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.

Description

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.

Code

function bogosort(array)
    while !ordered(array)
        shuffle(array)

Complexity

The expected complexity of bogosort is , because there are possible permutations of the input list.

Bozosort

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 .

Code

function bozosort(array)
    while !ordered(array)
        swap(array[random1], array[random2])

Sources

• 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