Bogosort (stupid sort, slowsort) is an algorithm used as a demonstration of the least effective approach to sort a list of values. Bogosort is only a theoretical concept, which has no use in practical applications.
The bogosort procedure is trivial – at first it checks, if the list is already sorted. If so, algorithm terminates. Otherwise it randomly shuffles the list and repeats the procedure.
function bogosort(array) while !ordered(array) shuffle(array)
The expected complexity of bogosort is , because there are possible permutations of the input list.
Closely related to bogosort is bozosort algorithm. Bozosort procedure at first checks, if the list is already sorted. If it is sorted, than it terminates. Otherwise it randomly swaps two elements of the array and repeats the procedure.
The expected complexity of bozosort is .
function bozosort(array) while !ordered(array) swap(array[random1], array[random2])
- GRUBER, Hermann, Markus HOLZER a Oliver RUEPP. Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms. Available at: http://www.hermann-gruber.com/data/fun07-final.pdf