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. Your welcome.

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 posative, 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

1. include<iostream>
2. 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