Bogosort - Related Algorithms

Related Algorithms

Goro sort
is a sorting algorithm introduced in the 2011 Google Code Jam. As long as the list is not in order, a subset of all elements is randomly permuted. If this subset is optimally chosen each time this is performed, the expected value of the total number of times this operation needs to be done is equal to the number of misplaced elements.
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. The running time analysis of Bozo Sort is more difficult, but some estimates are found in H. Gruber's analysis of perversely awful randomized sorting algorithms. O(n!) is found to be the expected average case.
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. The list is then inspected, and if it is not in order, the universe is destroyed. By the many-worlds interpretation of quantum physics, the quantum randomization spawns (where N is the number of random bits) universes and one of these will be such that this single shuffle had produced the list in sorted order.

Read more about this topic:  Bogosort

Other articles related to "related algorithms, algorithm":

Cheriyan–Mehlhorn/Gabow Algorithm - Related Algorithms
... Like this algorithm, Tarjan's strongly connected components algorithm also uses depth first search together with a stack to keep track of vertices that have not yet been assigned to a component, and ... However, in place of the second stack, Tarjan's algorithm uses a vertex-indexed array of preorder numbers, assigned in the order that vertices are first visited in the depth-first ...

Famous quotes containing the word related:

    Generally there is no consistent evidence of significant differences in school achievement between children of working and nonworking mothers, but differences that do appear are often related to maternal satisfaction with her chosen role, and the quality of substitute care.
    Ruth E. Zambrana, U.S. researcher, M. Hurst, and R.L. Hite. “The Working Mother in Contemporary Perspectives: A Review of Literature,” Pediatrics (December 1979)