2 ms·
This sounds a lot like BogoSort, which has an average-case running time of O(n * n!), basically exponential. Best-case is only O(n), though: http://en.wikiped
by nostrademons 17y ago
This sounds a lot like BogoSort, which has an average-case running time of O(n * n!), basically exponential. Best-case is only O(n), though:
http://en.wikipedia.org/wiki/Bogosort http://en.wikipedia.org/wiki/Bogosort
There is a variant called Quantum Bogosort, assuming the many-worlds hypothesis, which works like this:
1. Perform BogoSort
2. If the array is out of order, destroy the universe.
This has an average-case running time of O(n) for the universes that survive, at the cost of destroying n! universes. Destroying the universe is left as an exercise to the reader.
- amichail 17y agoAverage case is not that bad actually. Try coding it.
- nostrademons 17y agoUmm, factorial time generally means that for input sizes about 10-20, the problem essentially can't be computed in the lifetime of the known universe. Sorting 20 elements with BogoSort takes on the order of 46 quintillion operations.
- amichail 17y agoIt's less than exponential time.
- nostrademons 17y agoFactorial time is not less than exponential time, in a big-O sense. See Stirling's Approximation: http://en.wikipedia.org/wiki/Stirling%27s_approximation http://en.wikipedia.org/wiki/Stirling%27s_approximation
- amichail 17y agoThe expected running time is sub-cubic.
- rms 17y agoEdited for wrongness. http://en.wikipedia.org/wiki/Bogosort#Bozo_sort http://en.wikipedia.org/wiki/Bogosort#Bozo_sort
- nostrademons 17y agoThe difference between Bogosort and Bozosort is where the check for sortedness occurs - in BogoSort, you permute the whole array (by swapping individual pairs) and then check to see if it's in order, in Bozosort you swap the pairs and then check to see if it's in order. Amichail didn't specify which one he wanted.
- jibiki 17y agoNo, bozosort chooses, then swaps. Amisort chooses, checks if the elements are out of order, then swaps if they are. Totally different idea.