Comment by sanj
15 years ago
I always like the "shaking box" algorithm:
1. Check if list ordered. If it is, we're done!
2. Randomize order of list. Go back to step 1.
N!
15 years ago
I always like the "shaking box" algorithm:
1. Check if list ordered. If it is, we're done!
2. Randomize order of list. Go back to step 1.
N!
Worst case O(\inf), it's known as 'random sort' or 'bogosort'.
Funny thing, it can theoretically be O(1) on quantum computers, assuming the multiple-universe interpretation of quantum mechanics: http://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort ;).
My favorite presentation (http://c2.com/cgi/wiki?QuantumBogoSort) goes approximately like this:
1. Randomize the list. 2. If the list is not sorted, destroy the universe.
Is randomizing a list of n entities once is an O(n) operation. not sure how it would be done in O(1) on quantum computers.
The link that Dove gave suggests there's an idea of quantum randomization that will split our universe into n! universes in constant time.
This is usually known as bogosort. http://en.wikipedia.org/wiki/Bogosort
This is more commonly known as bogosort (http://en.wikipedia.org/wiki/Bogosort), and it's a good start for running time but isn't guaranteed to terminate. See my other comment for a link to something that goes one better than bogosort on running time.
If the shuffle is truly random eventually you will find that the list is sorted and the bogosort will terminate. If your shuffle is not truly random then it may likely never terminate.
Not true at all.
Given a uniform distribution over k discrete values (in this case permutations of the list), the expected probability of the next permutation is 1/k. This is not the same as saying that if you take k samples from the distribution, you are guaranteed to receive exactly one of each value. For any finite number n of samples, no matter how large, the probability of getting a given value tends towards 1 as n grows, but it only approaches it asymptotically. While the probability of not seeing any one value from the domain grows vanishingly small as n gets much larger than the number of possible values, it never hits zero. So even with a stochastically random source of list permutations, we cannot place a finite upper bound on a time in which bogosort is guaranteed to terminate.
It gets even worse with pseudorandom number generators — these display cyclical behavior over time (any good one will take quite a while to show it, but they all will), and you might have picked a seed for your PRNG that generates a cycle that never includes the sorted permutation.
So no, bogosort is not guaranteed to terminate. In practice, it has a reasonable chance of terminating for most inputs, and it will do so with an expected (not guaranteed!) runtime in O(n!) for a list of length n.
2 replies →
That's not right. True random sources make no guarantees, and nothing says they need to be exhaustive.