bogo-sort

2 definitions found

bogo-sort - Free On-line Dictionary of Computing (26 May 2007) :

  bogo-sort
  monkey sort
  
     <algorithm, humour> /boh"goh-sort"/ (Or "stupid-sort") The
     archetypical perversely awful algorithm (as opposed to
     bubble sort, which is merely the generic *bad* algorithm).
     Bogo-sort is equivalent to repeatedly throwing a deck of cards
     in the air, picking them up at random, and then testing
     whether they are in order.  It serves as a sort of canonical
     example of awfulness.  Looking at a program and seeing a dumb
     algorithm, one might say "Oh, I see, this program uses
     bogo-sort."
  
     Also known as "monkey sort" after the Infinite Monkey Theorem
     .
  
     Compare brute force, Lasherism.
  
     An implementation (http://stdout.org/~adam/psort).
  
     [Jargon File]
  
     (2002-04-07)
  

bogo-sort - Jargon File (4.4.4, 14 Aug 2003) :

  bogo-sort
   /boh`goh.sort'/, n.
  
     (var.: stupid-sort) The archetypical perversely awful algorithm (as
     opposed to bubble sort, which is merely the generic bad algorithm).
     Bogo-sort is equivalent to repeatedly throwing a deck of cards in the
     air, picking them up at random, and then testing whether they are in
     order. It serves as a sort of canonical example of awfulness. Looking
     at a program and seeing a dumb algorithm, one might say "Oh, I see,
     this program uses bogo-sort." Esp. appropriate for algorithms with
     factorial or super-exponential running time in the average case and
     probabilistically infinite worst-case running time. Compare bogus,
     brute force.
  
     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.