3 ms·
Show that this extremely simple sort has sub-cubic expected running time.
Pick two elements at random. If they are out of order, swap them.
How long will it take until the array is sorted?
UPDATE: To turn this into an algorithm, you will need to determine how to check whether the array is sorted.
- nostrademons 17y agoThis 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.
- jibiki 17y agoEach element can be swapped at most once with each other element. So the number of swaps is less than n choose 2, i.e., quadratic. (This does not mean that the run time is quadratic, since pairs can be chosen multiple times, and left alone each time because they are already in order.) EDIT: Whoops, I lied: 3,2,1 -> 2,3,1 -> 1,3,2 -> 1,2,3 2 and 3 switch twice. Anyways, the (whole number) quantity sum_{j=1,...,n}(|x_j - j|) seems to be decreasing under this sort, and it's initial value is O(n squared), so I guess the algorithm should have performance O(n squared), but it will be slower in reality because random choice is not O(1).