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 constant 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.
Implementation of step 2 is left as an exercise for the
reader.
(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 constant 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.
Implementation of step 2 is left as an exercise for the
reader.
Related:
- 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... - bubble sort: n. Techspeak for a particular sorting technique in
which pairs of adjacent values in the list to be sorted are
compared and interchanged if they are out of order;
thus, list entries `bubble upward' in the list until... - bubble sort n.
Techspeak for a particular sorting
technique in which pairs of adjacent values in the list to be
sorted are compared and interchanged if they are out of order;
thus, list entries `bubble upward' in the list until... - stupid-sort n.
Syn.
bogo-sort... - brute force adj.
Describes a primitive programming style,
one in which the programmer relies on the computer's... - stupid-sort: n. Syn. {bogo-sort}.
--
The AI Hackers... - naive adj.
1. Untutored in the perversities of some particular
program or system;
one who still tries to do things in an intuitive ... - pixel sort n.
[Commodore users] Any compression routine
which irretrievably loses valuable data in the process of
crunching it.
Disparagingly used for `lossy' methods such as JPEG... - fencepost error n.
1. [common] A problem with the discrete
equivalent of a boundary condition,
often exhibited in programs by iterative loops....
