Bogosort

In computer science, bogosort (also known as permutation sort and stupid sort) is a sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one that is sorted. It is not considered useful for sorting, but may be used for educational purposes, to contrast it with more efficient algorithms. The algorithm's name is a portmanteau of the words bogus and sort.

Two versions of this algorithm exist: a deterministic version that enumerates all permutations until it hits a sorted one, and a randomized version that randomly permutes its input and checks whether it is sorted. An analogy for the working of the latter version is to sort a deck of cards by throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted. In a worst-case scenario with this version, the random source is of low quality and happens to make the sorted permutation unlikely to occur.

Probabilistic analysis

Although Bogosort is primarily discussed as a pedagogical example of an inefficient sorting algorithm, it can also be connected to basic probability theory.

One way to analyze its expected behavior is to consider the probability of obtaining a sorted sequence after repeated random shuffles. This is analogous to the general formula for the probability of at least one success in a series of independent trials:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(\text{at least one success}) = 1 - (P(\text{failure in one trial}))^n}

Here, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} represents the number of independent shuffles (trials). In the context of Bogosort, a "success" corresponds to producing a sorted permutation, while a "failure" corresponds to producing an unsorted permutation. Since only one of the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n!} possible permutations is sorted, the probability of success in a single trial is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/n!} . Thus, the probability of obtaining a sorted list within Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} shuffles is:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(\text{sorted within } k \text{ shuffles}) = 1 - \left(1 - \tfrac{1}{n!}\right)^k}

This framing highlights the extreme inefficiency of Bogosort: even for modest values of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , the probability of success remains vanishingly small unless Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} is astronomically large.

Description of the algorithm

Pseudocode

The following is a description of the randomized algorithm in pseudocode:

function bogoSort(deck: List):
    while deck is not sorted:
        shuffle(deck)

C

An implementation in C:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <stddef.h>

void shuffle(int a[], int length) {
    int temp;
    int random;

    for (size_t i = 0; i < length; i++) {
        random = rand() % length;
        temp = a[random];
        a[random] = a[i];
        a[i] = temp;
    }
}

bool sorted(int a[], int length) {
    for (size_t i = 0; i < length - 1; i++) {
        if (a[i] > a[i + 1]) {
            return false;
        }
    }
    return true;
}

void bogoSort(int a[], int length) {
    while (!sorted(a, length)) {
        shuffle(a, length);
    }
}

int main(void) {
    int input[] = {68, 14, 78, 98, 67, 89, 45, 90, 87, 78, 65, 74};
    int size = sizeof(input) / sizeof(input[0]);

    srand((unsigned)time(NULL));

    bogoSort(input, size);

    printf("Sorted result:");
    for (size_t i = 0; i < size; i++) {
        printf(" %d", input[i]);
    }
    printf("\n");

    return 0;
}

Python

An implementation in Python:

import random

# this function checks whether or not the array is sorted
def is_sorted(a: list[int]) -> bool:
    for i in range(1, len(a)):
        if a[i] < a[i - 1]:
            return False
    return True

# this function repeatedly shuffles the elements of the array until they are sorted
def bogo_sort(a: list[int]) -> list[int]:
    while not is_sorted(a):
        random.shuffle(a)
    return a

# this function generates an array with randomly chosen integer values
def generate_random_array(size: int, min_val: int, max_val: int) -> list[int]:
    return [random.randint(min_val, max_val) for _ in range(size)]

if __name__ == "__main__":
    # the size, minimum value and maximum value of the randomly generated array
    size: int = 10
    min_val: int = 1
    max_val: int = 100
    random_array: list[int] = generate_random_array(size, min_val, max_val)
    print("Unsorted array:", random_array)
    sorted_arr = bogo_sort(random_array)
    print("Sorted array:", sorted_arr)

This code creates a random array - random_array - in generate_random_array that would be sorted by shuffling it in bogosort. All data in the array is natural numbers from 1 - 100.

Running time and termination

File:ExperimentalBogosort.png

Experimental runtime of bogosort

If all elements to be sorted are distinct, the expected number of comparisons performed in the average case by randomized bogosort is asymptotically equivalent to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (e-1)n!} , and the expected number of swaps in the average case equals Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n-1)n!} . The expected number of swaps grows faster than the expected number of comparisons, because if the elements are not in order, this will usually be discovered after only a few comparisons, no matter how many elements there are; but the work of shuffling the collection is proportional to its size. In the worst case, the number of comparisons and swaps are both unbounded, for the same reason that a tossed coin might turn up heads any number of times in a row.

The best case occurs if the list as given is already sorted; in this case the expected number of comparisons is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n - 1} , and no swaps at all are carried out.

For any collection of fixed size, the expected running time of the algorithm is finite for much 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 will almost surely eventually be chosen.

Related algorithms

Gorosort

An 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. Technically, Gorosort is not a sorting algorithm, but is instead an algorithm for permuting a list of items (whose true order is already known) so that they appear in order.

Bogobogosort

An algorithm that recursively calls itself with smaller and smaller copies of the beginning of the list to see if they are sorted. The base case is a single element, which is always sorted. For other cases, it compares the last element to the maximum element from the previous elements in the list. If the last element is greater or equal, it checks if the order of the copy matches the previous version, and if so returns. Otherwise, it reshuffles the current copy of the list and restarts its recursive check.

Bozosort

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 a bozosort is more difficult, but some estimates are found in H. Gruber's analysis of "perversely awful" randomized sorting algorithms. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n!)} is found to be the expected average case.

Worstsort

A pessimal sorting algorithm that is guaranteed to complete in finite time; however, its efficiency can be arbitrarily bad, depending on its configuration. The Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{worstsort}} algorithm is based on a bad sorting algorithm, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{badsort}} . The badsort algorithm accepts two parameters: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} , which is the list to be sorted, and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} , which is a recursion depth. At recursion level Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = 0} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{badsort}} merely uses a common sorting algorithm, such as bubblesort, to sort its inputs and return the sorted list. That is to say, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{badsort}(L, 0) = \texttt{bubblesort}(L)} . Therefore, badsort's time complexity is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^2)} if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k=0} . However, for any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k > 0} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{badsort}(L, k)} first generates Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} , the list of all permutations of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} . Then, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{badsort}} calculates Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{badsort}(P, k - 1)} , and returns the first element of the sorted Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} . To make Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{worstsort}} truly pessimal, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} may be assigned to the value of a computable increasing function such as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f: \N \to \N} (e.g. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = A(n, n)} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} is Ackermann's function). Therefore, to sort a list arbitrarily badly, one would execute Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{worstsort}(L, f) = \texttt{badsort}(f(\texttt{length}(L)))} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{length}(L)} is the number of elements in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} . The resulting algorithm has complexity Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \Omega\left(\left(n!^{(f(n))}\right)^2\right)} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n!^{(m)} = (\dotso((n!)!)!\dotso)!} = factorial of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} iterated Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} times. This algorithm can be made as inefficient as one wishes by picking a fast enough growing function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} .

Slowsort

A different humorous sorting algorithm that employs a misguided divide-and-conquer strategy to achieve massive complexity.

Bozobogosort

A sorting algorithm that only works if the list is already in order, otherwise, the conditions of miracle sort are applied.

Quantum bogosort

A hypothetical sorting algorithm based on bogosort, created as an in-joke among computer scientists. The algorithm generates a random permutation of its input using a quantum source of entropy, checks if the list is sorted, and, if it is not, destroys the universe. Assuming that the many-worlds interpretation holds, the use of this algorithm will result in at least one surviving universe where the input was successfully sorted in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)} time.

See also

• Las Vegas algorithm
• Stooge sort

External links

• BogoSort on WikiWikiWeb
• Inefficient sort algorithms
• Bogosort: an implementation that runs on Unix-like systems, similar to the standard sort program.
• Bogosort and jmmcg::bogosort: Simple, yet perverse, C++ implementations of the bogosort algorithm.
• Bogosort NPM package: bogosort implementation for Node.js ecosystem.
• Max Sherman Bogo-sort is Sort of Slow, June 2013