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

## Contents

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

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

// [email protected]

#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;

}

### 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:

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.

#### 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):

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

//[email protected]

//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;

}

### 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:

(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 '())

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

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

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