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)