Anonymous user
User talk:MichaelChrisco: Difference between revisions
→Bead sort: a Unique Solution
| (3 intermediate revisions by the same user not shown) | |||
Line 1:
Thanks for squelching that spam. (Google Translate says it was some kind of advert for a Russian factory. Inappropriate for here for sure.) –[[User:Dkf|Donal Fellows]] 08:41, 27 July 2010 (UTC)
:ya no kidding. You are welcome.
===Bead sort: positive, zero and negative===
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===
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(
I intend to prove them wrong:
Line 41 ⟶ 194:
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.
[[File:
| |||