Bogosort definition

Bogosort





Home | Index


We love those sites:

2 definitions found

From Jargon File (4.3.1, 29 Jun 2001) [jargon]:

  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}, {lasherism}.
  
     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 it is sorted requires O(n)
     time). Implementation of step 2 is left as an exercise for the reader.
  
  

From The Free On-line Dictionary of Computing (27 SEP 03) [foldoc]:

  bogo-sort
       
           /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://www.stdout.org/~adam/psort)}.
       
          [{Jargon File}]
       
          (2002-04-07)
       
       

















Powered by Blog Dictionary [BlogDict]
Kindly supported by Vaffle Invitation Code Get a Freelance Job - Outsource Your Projects | Threadless Coupon
All rights reserved. (2008-2024)