# 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: positive, zero and negative[edit]

Posted the work here: http://csinsider.homeip.net/index.php/User_talk:Michaelc Further work will be to:

- Create a list structure in bead sort and do analysis on performance
- Do a complete performance analysis with other sorting algorithms in different data sets
- I have an Idea how to make this sort even faster but I will have to keep that a secret for now

<lang cpp> //combination of both positive and negative bead sort (with zeros) //positive bead sort = O(1/2n) where n is the sumation of all positive integers //negative bead sort = O(1/2|n|) where n is the absolute value of the summation of all negative integers //count zeros and insert = O(z) where z is number of zeros //so all in all, the bead sort is still (O(S) where is is the summation of negative and positive bead sort algorithms //space complexity is now O(5n) where 1 array is set and the others are expandable. if lists were used, it could //probably be faster and better for insertion later but since I am only proving correctness, this will do.

//By Michael Chrisco // michaelachrisco@gmail.com

- include<iostream>
- include<vector>

using namespace std;

void distribute_neg( int dist, vector<int> &List)//in theory makes *beads* go down into different buckets using gravity. { dist=-dist; //resets to positive number for implamentation

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 negative

void distribute_pos( 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 positive
void sort(vector<int> &List){
int i;
int zeros=0;
vector<int> list;
vector<int> list_pos;
vector<int> sorted;
vector<int> sorted_pos;
cout << "#1 Beads falling down: ";
for (i=0; i < List.size(); i++)
if (List[i] < 0)
distribute_neg (List[i], list);
else if (List[i] > 0)
distribute_pos(List[i], list_pos);
else
zeros++;

cout << endl;

cout <<endl<< "Beads on their sides: "; for (i=0; i < list.size(); i++) cout << " " << list[i]; cout << endl;

cout <<endl<< "Beads on their sides positive: "; for (i=0; i < list_pos.size(); i++) cout << " " << list_pos[i]; cout << endl; //second part

cout << "#2 Beads right side up: "; for (i=0; i < list.size(); i++) distribute_neg (list[i], sorted);

for (i=0; i < list_pos.size(); i++) distribute_pos(list_pos[i], sorted_pos); cout << endl;

cout << endl;

cout <<endl<< "Sorted list/array neg";
for (i=0; i < sorted.size(); i++)
cout << " " << sorted[i];
cout << endl;

cout <<endl<< "Sorted list/array pos"; for (i=0; i < sorted_pos.size(); i++) cout << " " << sorted_pos[i]; cout << endl;

//combine two at end. //In theory, a list for both positive and negative structures would give better performance at the end, combining the //two lists in O(1) time. You may chose to do so if you wish. The same goes with zeros.

while (zeros > 0) { sorted_pos.push_back(0); zeros--; }

i=sorted.size()-1; while (i >= 0) { sorted_pos.push_back(sorted[i]); i--; }

cout <<endl<< "Sorted list/array"; for (i=0; i < sorted_pos.size(); i++) cout << " " << sorted_pos[i]; cout << endl;

}

int main(){
int myints[] = {-1, -4, -3, 1, 4, 3, 0};
vector<int> here_be_dragons (myints, myints + sizeof(myints) / sizeof(int) );

sort(here_be_dragons);

return 0;

} </lang>

### Bead sort: An update[edit]

In the wikipedia page it states that:
Both digital and analog hardware implementations of bead sort can achieve a sorting time of O(n); however, the implementation of this algorithm tends to be significantly slower in software and can only be used to sort lists of **positive** integers. Also, it would seem that even in the best case, the algorithm requires O(2n) space.

I intend to prove them wrong:

<lang cpp> void distribute( int dist, vector<int> &List)//in theory makes *beads* go down into different buckets using gravity. { dist=-dist; //resets to positive number for implamentation

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;

} } //same exact main as below. </lang>

#### Output:[edit]

- 1 Beads falling down:

Beads on their sides: -3 -2 -2 -1

- 2 Beads right side up:

Sorted list/array -4 -3 -1

### Bead sort: a Unique Solution[edit]

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(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:[edit]

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[edit]

- 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[edit]

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

## Javascript / HTML bean sort demo[edit]

Hello! I decided to attempt to implement this sort on my own, and added a display system to see the process in two steps.

The demo page for this is here -> [1] (http://betagammaepsilon.com/misc/beans.html)

but here is the main code for the distribution and sort

<lang javascript>

//global bank array var bank = new Array();

function distribute( beans ){

// if there are more beans than array slots, // make the array longer to accomidate the beans // if we don't have any beans, start our array with // the first number if ( bank.length == 0 ){ temp = new Array();

for(i = 0; i < beans; i++){ temp[i] = 0; } bank = temp; }else{ // if a bean has more rows than our bank, add more rows if ( beans > bank.length ){ //increase array by bank.length + beans temp = new Array(); for(i = 0; i < beans; i++){ if(i < bank.length){

temp[i] = bank[i]; }else{ temp[i] = 0; // start the row with one bean }

} // swap the arrays bank = temp; } }

// now distrubute the beans // add 1 to each row of beans that our number adds to // example: 3 would add 1 bean to the first three rows for(i = 0; i < beans; i++){ bank[i] = parseInt(bank[i]) + 1; }

}

// this function will add an array of numbers to the "bank"

function beanSort( list ){

bank = new Array(); // clear list for(a = 0; a < list.length; a++){

distribute(list[a]); // add bean to the bank

}

}

// Example useage

var sample = new Array(1,4,3,10,6);

beanSort(sample); // adds sample to bank, stored in bank

beanSort(bank); // sorts the bank in the bank

// an alert(bank) would show the final sorted array

</lang>

-Jeff Blanchette

## Sorry for missing you in IRC[edit]

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 (creating the picture and posting it up on the wiki). 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.
- 2000 hits within 1 day of posting! Wow thanks!
- According to the analytics data, someone added it to Reddit, which appears to be where the hits came from. (Also, sign your posts with --~~~~) --Michael Mol 07:56, 24 August 2010 (UTC)
- Ya i put that up a few days ago but I didn't think that it would get this kind of traffic. Thanks for the heads up about the sign post. --MichaelChrisco 02:57, 25 August 2010 (UTC)

- According to the analytics data, someone added it to Reddit, which appears to be where the hits came from. (Also, sign your posts with --~~~~) --Michael Mol 07:56, 24 August 2010 (UTC)

- 2000 hits within 1 day of posting! Wow thanks!

- not a problem. I just wanted to show a little illustration on this new(ish?) sorting algorithm. Figured it out on my own (creating the picture and posting it up on the wiki). 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.