User talk:MichaelChrisco: Difference between revisions

Content added Content deleted

Inline

@@ Line 6: / 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.
+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>