Re:Bogo-bogosort
by fragsworth on Saturday December 28, 2013 @07:48PM
(#6977472)
Here is a "distributed" sorting algorithm that requires even less thinking - you don't even have to write a shuffling algorithm!
1) Start with an empty string.
2) Increment the string in such a way that will eventually generate all strings.
3) Give the string (and your unsorted array) to a processor that attempts to run the string as a program and go back to step 2.
When a processor is given a program, if the output contains all the elements of A and the output is sorted, stop everything! You've sorted the array.
It requires O(n^m) processors, where n is the number of characters possible in a program, and m is the string length of the code that finds the solution. Lots of the processors will be stuck in infinite loops.
1) Start with an empty string.
2) Increment the string in such a way that will eventually generate all strings.
3) Give the string (and your unsorted array) to a processor that attempts to run the string as a program and go back to step 2.
When a processor is given a program, if the output contains all the elements of A and the output is sorted, stop everything! You've sorted the array.
It requires O(n^m) processors, where n is the number of characters possible in a program, and m is the string length of the code that finds the solution. Lots of the processors will be stuck in infinite loops.