Absurd algorithms (was:RE: Programmer's conundrums)

On 4/14/06, Fred Cisin <cisin at xenosoft.com> wrote: It's called bogosort. It's O(N!) if your random number generator is perfect. Pseudocode from the wikipedia entry: --------------------------------------------------------------------- function bogosort(array) while not is_sorted(array) array := random_permutation(array) --------------------------------------------------------------------- The only worse (speed wise) sorting algorithm that I know of is what I call the infinitysort(). It just waits for random physical processes to sort the array. It is O((BN)!) where B is the size of the objects in bits. pseudocode representation is... --------------------------------------------------------------------- function infinitysort(array) while (not is_sorted(array)) or contains_different_elements(array) wait --------------------------------------------------------------------- You could greatly improve this algorithm by changing wait to "generate a random bit pattern the same size as array" The fastest sort I know of is the O(1) sort called nosort(). It's pseudocode is --------------------------------------------------------------------- function nosort(array) --------------------------------------------------------------------- It's only problem is that its probability of getting the right answer is equal to the probability that the array is already sorted.