|
Bogosort is a particularly ineffective sorting algorithm. Used to sort a deck of cards, it would consist of throwing the deck in the air, picking the cards up at random, and testing for order. If they are not in order, repeat. It is named after the humorous term quantum bogodynamics and ultimately, the word bogus. Other names are stupid sort, bozo sort, blort sort, monkey sort, random sort and drunk man sort. In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...
Category: Possible copyright violations ...
Quantum bogodynamics is a humorous theory that characterises the universe in terms of sources of fictional fundamental particles, bogons. ...
Bogosort is not a stable sort. In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...
Pseudocode function bogosort(array) repeat array := random_permutation(array) until is_sorted(array)
Running time and termination This sorting algorithm is probabilistic in nature. If all elements to be sorted are distinct, the expected complexity is O(n × n!). The exact expected running time depends on how many different element values occur, and how often each of them occurs, but for non-trivial cases the expected running time is super-exponential in n since n! outgrows an. It terminates for the same reason that the infinite monkey theorem holds; there is some probability of getting the right permutation, so given an unbounded number of tries it must eventually find it. In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...
According to the second Borel-Cantelli lemma, given enough time, a chimpanzee like this one typing at random will surely type out a copy of one of Shakespeares plays. ...
It should be noted that with real-world pseudo-random number algorithms, which have a finite number of states and are not in any case actually random, the algorithm may never terminate for certain inputs. A pseudo-random number is a number belonging to a sequence which appears to be random, but can in fact be generated by a finite computation. ...
// About Bees This article is about completely random and illogical things. ...
Caveat If you use the same random number algorithm and the same starting seed to sort the array as was used to randomize the array, you can be surprised by successfully sorting in one iteration. This is caused by the failure of a computer to produce random numbers. Do not expect such a quick resolution with true random numbers or another seed.
Related algorithms
Bozo sort Bozo sort is another sorting algorithm based on random numbers. If the list is not in order, it picks two items at random and swaps them, then checks to see if the list is sorted. It also faces the same pseudo-random problems as bogosort—it may never terminate.
Quantum Bogosort An in-joke among some computer scientists is that quantum computing could be used to effectively implement a bogosort with a time complexity of O(n). It uses true quantum randomness to randomly permute the list. By the many-worlds interpretation of quantum physics, the quantum randomization spawns an infinite array of universes and some of these will be such that the single shuffle had produced the list in sorted order because the total number of distinct orderings, though large, is not infinite. The list is then tested for sortedness (requiring n-1 comparisons); should it be out of order, the computer triggers its "destroy universe" operation. Only in the surviving universes will there be observers to see that the randomisation worked first time and that the list is in sorted order. Molecule of alanine used in NMR implementation of error correction. ...
// The many-worlds interpretation of quantum mechanics or MWI, also known as the relative state formulation, theory of the universal wavefunction, many-universes interpretation or just many worlds is an interpretation of quantum mechanics that claims to resolve all the paradoxes of quantum theory by allowing every possible outcome to...
Note, however, that even here there is no free lunch -- while this algorithm is O(n) in time, permuting the list requires that we consume O(n log n) bits of quantum randomness.
Some caution is needed over the choice of algorithms suitable for adaptation to such a quantum computer. For instance, the bozosort is very unlikely to succeed in one iteration and for many inputs (in which there is more than just one pair of elements out of order) it cannot succeed in one iteration. For those inputs, observers would be surprised by mysterious failures of the computer or improbable accidents preventing its operation because all universes in which it did operate are destroyed.
External links |
Feeds |
Contact