OT: was: Programmer's conundrums
ploopster at gmail.com
Fri Apr 14 09:41:56 CDT 2006
a.carlini at ntlworld.com wrote:
> Chuck Guzis wrote:
>> Wonder why everyone mentions "bubble sort" when they mean a
>> relatively inefficient sort?
> I'm sure Knuth mentions "random-sort" as being worse (randomly
> shuffle elements, check if order correct, if not then repeat).
I've heard that called "bogosort". The Jargon File has an interesting
version called "quantum bogosort". Here's a quote:
"A spectacular variant of bogo-sort has been proposed which has the
interesting property that, if the Many Worlds interpretation of quantum
mechanics is true, it can sort an arbitrarily large array in linear
time. (In the Many-Worlds model, the result of any quantum action is to
split the universe-before into a sheaf of universes-after, one for each
possible way the state vector can collapse; in any one of the
universes-after the result appears random.) The steps are: 1. Permute
the array randomly using a quantum process, 2. If the array is not
sorted, destroy the universe (checking that the list is sorted requires
O(n) time). Implementation of step 2 is left as an exercise for the reader."
More information about the cctalk