OT: was: Programmer's conundrums

Sridhar Ayengar 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."

8-)

Peace...  Sridhar



More information about the cctalk mailing list