User talk:MichaelChrisco: Difference between revisions
No edit summary |
m (newLISP non-working impl. (work in progress)) |
||
Line 125: | Line 125: | ||
sys 0m0.002s |
sys 0m0.002s |
||
===For those who what a challenge=== |
|||
I dont feel like doing the newLISP implementation at the moment but here is what I was working on: |
|||
<lang newLISP> |
|||
(define (distribute X L List2) |
|||
(while (< (length L) X) (push 0 L));;make sure that you can add the X to the list |
|||
;; (let (List2 '())) for some reason this list does not work. |
|||
(for (y 0 (- X 1) 1) (let (POS (+ (L y) 1))(println "P: "POS) ;;POS->position of pointer |
|||
(push POS List2 )))List2);;create new list adding 1 to each element in the origional. |
|||
;;(define (over L) |
|||
;; (let (SORTED_LIST '())) |
|||
;; (for (z 0 (- (length L) 1) 1) (SORTED_LIST (distribute (L z) '())))) |
|||
(define Y '(1 2)) |
|||
(define T '()) |
|||
(distribute 10 Y T) |
|||
(define Sorted '()) |
|||
;;now we try it over a list |
|||
(define (over L);;do recursion here |
|||
(if (empty? L) (print "a:") (over (pop L)))) |
|||
(over '(4 4 5)) |
|||
(over '()) |
|||
</lang> |
|||
Its a work in progress. So if your lisp savvy, try it out and tell me what you get..... |
Revision as of 22:48, 22 August 2010
Thanks for squelching that spam. (Google Translate says it was some kind of advert for a Russian factory. Inappropriate for here for sure.) –Donal Fellows 08:41, 27 July 2010 (UTC)
- ya no kidding. Your welcome.
Bead sort: a Unique Solution
Ive been working on an elegant solution to a paper I found on the internet. Its called Bead-sort http://en.wikipedia.org/wiki/Bead_sort. I am not sure that this is an original idea but I seem to have implemented it in C++. Why C++.....because I couldn't do it in Newlisp (yet!). I think that the elegance of this algorithm is cool (as it was an A HA!! moment for me). It uses a distribution algorithm to distribute the "beads" one at a time though "buckets". These buckets, in turn, are the accumulators (or the after affects of gravity on bead sort).
I was trying to figure out a solution into turning them back into a list/array sorted format when it hit me! Use the same algorithm twice! So i did. And it worked! It works because gravity works both ways.
The following code is open source. Do what you want with it (just gimme a little credit and the original authors of the paper):
<lang cpp>
//this algorithm only works with positive, whole numbers. It can be made to work with other numbers but the performance would be horrific. //its a proof of concept. For actual sorting, it probably has worse time and space complexity than some algorithms. //O(n) time complexity where n is the summation of the whole list to be sorted. //O(3n) space complexity. There are three lists that I created. 2 on the fly.
//Michael Chrisco Aug. 22, 2010 //michaelachrisco@gmail.com
- include<iostream>
- include<vector>
using namespace std;
void distribute( int dist, vector<int> &List)//in theory makes *beads* go down into different buckets using gravity. {
if (dist > List.size() ) {
List.resize(dist,0);//can be done differently but *meh*
}
for (int i=0; i < dist; i++)
{
List[i]=List[i]+1;
} } //end of distribute
int main(){
vector<int> list;
vector<int> list2;
int myints[] = {5,3,1,7,4,1,1};
vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );
cout << "#1 Beads falling down: "; for (int i=0; i < fifth.size(); i++)
distribute (fifth[i], list);
cout << endl;
cout <<endl<< "Beads on their sides: "; for (int i=0; i < list.size(); i++) cout << " " << list[i]; cout << endl;
//second part
cout << "#2 Beads right side up: "; for (int i=0; i < list.size(); i++) distribute (list[i], list2);
cout << endl;
cout <<endl<< "Sorted list/array";
for (int i=0; i < list2.size(); i++)
cout << " " << list2[i];
cout << endl;
return 0;
}
</lang>
Output:
Beads falling down:
Beads on their sides: 7 4 4 3 2 1 1 Beads right side up:
Sorted list/array 7 5 4 3 1 1 1
Time trials
- small dataset:
time ./test
Sorted list/array 7 5 4 3 1 1 1
real 0m0.011s
user 0m0.001s
sys 0m0.002s
- larger dataset
Sorted list/array 1000 7 5 4 3 1 1
real 0m0.009s
user 0m0.001s
sys 0m0.002s
- even larger
Sorted list/array 9999 1000 7 7 6 6 5 5 5 4 4 4 4 3 3 3 3 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
real 0m0.019s
user 0m0.003s
sys 0m0.002s
For those who what a challenge
I dont feel like doing the newLISP implementation at the moment but here is what I was working on:
<lang newLISP>
(define (distribute X L List2)
(while (< (length L) X) (push 0 L));;make sure that you can add the X to the list
- (let (List2 '())) for some reason this list does not work.
(for (y 0 (- X 1) 1) (let (POS (+ (L y) 1))(println "P: "POS) ;;POS->position of pointer (push POS List2 )))List2);;create new list adding 1 to each element in the origional.
- (define (over L)
- (let (SORTED_LIST '()))
- (for (z 0 (- (length L) 1) 1) (SORTED_LIST (distribute (L z) '()))))
(define Y '(1 2))
(define T '())
(distribute 10 Y T)
(define Sorted '())
- now we try it over a list
(define (over L);;do recursion here (if (empty? L) (print "a:") (over (pop L))))
(over '(4 4 5))
(over '())
</lang>
Its a work in progress. So if your lisp savvy, try it out and tell me what you get.....