Anonymous user
User talk:MichaelChrisco: Difference between revisions
Bead sort C++ code
((new?) sorting algorithm implamentation!!!!! I got it to work!!!! Bead sort!) |
(Bead sort C++ code) |
||
Line 6:
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
<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
#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>
| |||