User talk:MichaelChrisco

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. You are 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):

//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(2n) 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

//Based off of paper here: http://www.cs.auckland.ac.nz/~jaru003/research/publications/journals/beadsort.pdf

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 you are lisp savvy, try it out and tell me what you get.....

Sorry for missing you in IRC

We're all lurkers, and often our IRC clients are in the channel while we're away. IRC is very much an asynchronous communications medium, with an occasional upgrade to real-time chat. --Michael Mol 01:50, 23 August 2010 (UTC)

not a problem. I just wanted to show a little illustration on this new(ish?) sorting algorithm. Figured it out on my own. Ill work on it when i have time. I cant believe how many people are interested in this though... over 1000+ hits in a matter of 5 hours is amazing. At the very least, now more people know about the site.