View source for Bogosort

{{Short description|Sorting algorithm}}
{{Use dmy dates|date=December 2021}}
{{Infobox Algorithm
|image =
|class=[[Sorting]]
|data=[[Array data structure|Array]]
|time=Unbounded (randomized version), <math>\Omicron(n \times n!)</math> (deterministic version)
|average-time=<math>\Theta(n \times n!)</math><ref name="Fun07"/>
|best-time=<math>\Omega(n)</math><ref name="Fun07"/>
|space=<math>\Omicron(1)</math>
}}

In [[computer science]], '''bogosort'''<ref name="Fun07"/><ref name="KSFS">{{citation
 | last1 = Kiselyov
 | first1 = Oleg
 | last2 = Shan
 | first2 = Chung-chieh
 | last3 = Friedman
 | first3 = Daniel P.
 | last4 = Sabry
 | first4 = Amr
 | contribution = Backtracking, interleaving, and terminating monad transformers: (functional pearl)
 | doi = 10.1145/1086365.1086390
 | pages = 192–203
 | series = SIGPLAN Notices
 | title = Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05)
 | url = http://www.dicta.org.uk/programming/LogicT.pdf
 | year = 2005
 | s2cid = 1435535
 | access-date = 22 June 2011
 | archive-url = https://web.archive.org/web/20120326002456/http://www.dicta.org.uk/programming/LogicT.pdf
 | archive-date = 26 March 2012
 | url-status = dead
 }}</ref> (also known as '''permutation sort''' and '''stupid sort'''<ref>E. S. Raymond. "bogo-sort". ''The New Hacker’s Dictionary''. MIT Press, 1996.</ref>) is a [[sorting algorithm]] based on the [[generate and test]] paradigm. The function successively generates [[permutation]]s 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''.<ref>{{Cite web|title=bogosort|url=https://xlinux.nist.gov/dads/HTML/bogosort.html|access-date=2020-11-11|website=xlinux.nist.gov}}</ref>

Two versions of this algorithm exist: a deterministic version that enumerates all permutations until it hits a sorted one,<ref name="KSFS"/><ref name="Naish86">{{citation |last=Naish |first=Lee |title=Proceedings of the Third International Conference on Logic Programming |volume=225 |pages=624–634 |year=1986 |series=[[Lecture Notes in Computer Science]] |contribution=Negation and quantifiers in NU-Prolog |publisher=Springer-Verlag |doi=10.1007/3-540-16492-8_111|isbn=978-3-540-16492-0 }}.</ref> and a [[randomized algorithm|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. 

==Description of the algorithm==

=== Pseudocode ===
The following is a description of the randomized algorithm in [[pseudocode]]:

 '''while''' deck '''is not''' sorted:
     shuffle(deck)

=== C ===
An implementation in [[C (programming language)|C]]:<syntaxhighlight lang="c" line="1">
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// executes in-place bogo sort on a given array
static void bogo_sort(int* a, int size);
// returns 1 if given array is sorted and 0 otherwise
static int is_sorted(int* a, int size);
// shuffles the given array into a random order
static void shuffle(int* a, int size);

void bogo_sort(int* a, int size) {
    while (!is_sorted(a, size)) {
        shuffle(a, size);
    }
}

int is_sorted(int* a, int size) {
    for (int i = 0; i < size-1; i++) {
        if (a[i] > a[i+1]) {
            return 0;
        }
    }
    return 1;
}

void shuffle(int* a, int size) {
    int temp, random;
    for (int i = 0; i < size; i++) {
        random = (int) ((double) rand() / ((double) RAND_MAX + 1) * size);
        temp = a[random];
        a[random] = a[i];
        a[i] = temp;
    }
}

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

    // initialize pseudo-random number generator
    srand(time(NULL));

    bogo_sort(input, size);

    // sorted result: 14 45 65 67 68 74 78 78 87 89 90 98
    printf("sorted result:");
    for (int i = 0; i < size; i++) {
        printf(" %d", input[i]);
    }
    printf("\n");

    return 0;
}
</syntaxhighlight>

=== Python ===
An implementation in [[Python (programming language)|Python]]:

<syntaxhighlight lang="python">
import random


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


# this function repeatedly shuffles the elements of the array until they are sorted
def bogo_sort(random_array):
    while not is_sorted(random_array):
        random.shuffle(random_array)
    return random_array


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


# the size, minimum value and maximum value of the randomly generated array
size = 10
min_val = 1
max_val = 100
random_array = generate_random_array(size, min_val, max_val)
print("Unsorted array:", random_array)
sorted_arr = bogo_sort(random_array)
print("Sorted array:", sorted_arr)
</syntaxhighlight>

This code assumes that {{code|data}} is a simple, mutable, array-like data structure—like Python's built-in {{code|list}}—whose elements can be compared without issue.

==Running time and termination==
[[File:ExperimentalBogosort.png|thumb|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 [[Asymptotic analysis|asymptotically equivalent to]] {{math|(''e'' − 1)''n''!}}, and the expected number of swaps in the average case equals {{math|(''n'' − 1)''n''!}}.<ref name="Fun07">{{citation
 | last1 = Gruber | first1 = H.
 | last2 = Holzer | first2 = M.
 | last3 = Ruepp | first3 = O.
 | contribution = Sorting the slow way: an analysis of perversely awful randomized sorting algorithms
 | doi = 10.1007/978-3-540-72914-3_17
 | pages = 183–197
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007
 | date = 2007
 | url = http://www.hermann-gruber.com/pdf/fun07-final.pdf
 | volume = 4475| isbn = 978-3-540-72913-6
 }}.</ref> 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 {{math|''n'' − 1}}, and no swaps at all are carried out.<ref name="Fun07"/>

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==
{{glossary}}<!--{{term}} adds its argument as an element id, so explicit anchors are unnecessary-->
{{term|Gorosort}}
{{defn|A sorting algorithm introduced in the 2011 [[Google Code Jam]].<ref>[https://github.com/google/coding-competitions-archive/tree/main/codejam/2011/qualification_round/gorosort Google Code Jam 2011, Qualification Rounds, Problem D]</ref> 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.}}
{{anchor|Bogobogosort}}
{{term|Bogobogosort}}
{{defn|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.<ref>[http://www.dangermouse.net/esoteric/bogobogosort.html Bogobogosort]</ref>
<!-- Bogobogosort needs to be implemented recursively, as in the iterative version it is too easy to optimize out the second bogo. -->}}
{{term|Bozosort}}
{{defn|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.<ref name="Fun07"/> {{math|O(''n''!)}} is found to be the expected average case.
<!--It also faces the same pseudo-random problems as bogosort—it may never terminate in a real-world implementation.-->}}
{{term|Worstsort}}
{{defn|1=A [[wiktionary:pessimal|pessimal]] sorting algorithm that is guaranteed to complete in finite time; however, its efficiency can be arbitrarily bad, depending on its configuration. The {{math|worstsort}} algorithm is based on a bad sorting algorithm, {{math|badsort}}. The badsort algorithm accepts two parameters: {{mvar|L}}, which is the list to be sorted, and {{mvar|k}}, which is a recursion depth. At recursion level {{math|1={{var|k}} = 0}}, {{math|badsort}} merely uses a common sorting algorithm, such as [[Bubble sort|bubblesort]], to sort its inputs and return the sorted list. That is to say, {{math|1=badsort({{var|L}}, 0) = bubblesort({{var|L}})}}. Therefore, badsort's time complexity is {{math|O({{var|n}}{{sup|2}})}} if {{math|1={{var|k}} = 0}}. However, for any {{math|{{var|k}} > 0}}, {{math|badsort({{var|L}}, {{var|k}})}} first generates {{mvar|P}}, the list of all permutations of {{mvar|L}}. Then, {{math|badsort}} calculates {{math|badsort({{var|P}}, {{var|k}} − 1)}}, and returns the first element of the sorted {{mvar|P}}. To make {{math|worstsort}} truly pessimal, {{mvar|k}} may be assigned to the value of a computable increasing function such as <math>f\colon\N \to \N</math> (e.g. {{math|1={{var|f}}({{var|n}}) = {{var|A}}({{var|n}}, {{var|n}})}}, where {{mvar|A}} is [[Ackermann's function]]).  Therefore, to sort a list arbitrarily badly, one would execute {{math|1=worstsort({{var|L}}, {{var|f}}) = badsort({{var|L}}, {{var|f}}(length({{var|L}})))}}, where {{math|length({{var|L}})}} is the number of elements in {{mvar|L}}. The resulting algorithm has complexity <math display="inline">\Omega\left(\left(n!^{(f(n))}\right)^2\right)</math>, where <math>n!^{(m)} = (\dotso((n!)!)!\dotso)!</math> = factorial of {{mvar|n}} iterated {{mvar|m}} times. This algorithm can be made as inefficient as one wishes by picking a fast enough growing function {{mvar|f}}.<ref>{{Cite arXiv |eprint = 1406.1077|last1 = Lerma|first1 = Miguel A.|title = How inefficient can a sort algorithm be?|class = cs.DS|year = 2014}}</ref>}}
{{term|[[Slowsort]]}}
{{defn|A different humorous sorting algorithm that employs a misguided divide-and-conquer strategy to achieve massive complexity.}}
{{term|Quantum bogosort}}
{{defn|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 {{math|O({{var|n}})}} time.<ref>{{cite journal |author=The Other Tree |date=23 October 2009 |title=Quantum Bogosort |url=https://mathnews.uwaterloo.ca/wp-content/uploads/2014/08/v111i3-compressed.pdf#page=13 |archive-url=https://web.archive.org/web/20200705214046/http://mathnews.uwaterloo.ca/wp-content/uploads/2014/08/v111i3-compressed.pdf |archive-date=2020-07-05 |url-status=live |journal=MathNEWS |volume=111 |issue=3 |page=13 |access-date=20 March 2022}}</ref>}}
{{term|Miracle sort}}
{{defn|A sorting algorithm that checks if the array is sorted until a [[miracle]] occurs. It continually checks the array until it is sorted, never changing the order of the array.<ref>{{Cite web |title=Miracle Sort |work=The Computer Science Handbook |url=https://www.thecshandbook.com/Miracle_Sort |access-date=2022-09-09}}</ref> Because the order is never altered, the algorithm has a hypothetical time complexity of {{math|''O''(''∞'')}}, but it can still sort through events such as miracles or [[single-event upset]]s. Particular care must be taken in the implementation of this algorithm as [[optimizing compiler]]s may simply transform it into a [[while(true)]] loop. However, the best case is {{math|''O''(''n'')}}, which happens on a sorted list. Since it only makes comparisons, it is both strictly in-place and stable.}}
{{term|Bozobogo sort}}
{{defn|A sorting algorithm that only works if the list is already in order, otherwise, the conditions of miracle sort are applied.}}
{{term|Divine sort}}
{{defn|A sorting algorithm that takes a list and decides that because there is such a low probability that the list randomly  occurred in its current permutation (a probability of 1/n!, where n is the number of elements), there must have been a reason for the list's order. Therefore, it should be considered sorted in a way we don't understand, and we do not have any right to sort it to our beliefs, as if it were sorted "as God intended." Also known as Intelligent Design sort.<ref>{{Cite web |title=Intelligent Design Sort |work=www.dangermouse.net|url=https://www.dangermouse.net/esoteric/intelligentdesignsort.html |access-date=2024-11-06}}</ref>}}
{{glossary end}}

==See also==
* [[Las Vegas algorithm]]
* [[Stooge sort]]
==References==
{{reflist}}

==External links==
{{wikibooks|Algorithm Implementation|Sorting/Bogosort|Bogosort}}
* [[c2:BogoSort|BogoSort]] on [[WikiWikiWeb]]
* [https://web.archive.org/web/20131210012102/http://richardhartersworld.com/cri_d/cri/2001/badsort.html Inefficient sort algorithms]
* [http://www.lysator.liu.se/~qha/bogosort/ Bogosort]: an implementation that runs on [[Unix-like]] systems, similar to the standard [[sort (Unix)|sort]] program.
* [https://archive.today/20130103015524/http://github.com/versesane/algorithms-and-data-structures-in-c/tree/master/bogosort.c Bogosort] and [https://web.archive.org/web/20221119040408/http://libjmmcg.cvs.sourceforge.net/viewvc/libjmmcg/libjmmcg/core/bogo_sort.hpp jmmcg::bogosort]: Simple, yet perverse, C++ implementations of the bogosort algorithm.
* [https://github.com/spugachev/random-sort Bogosort NPM package]: bogosort implementation for Node.js ecosystem.
* Max Sherman [https://sites.math.washington.edu/~morrow/336_13/papers/max.pdf Bogo-sort is Sort of Slow], June 2013
{{sorting}}

[[Category:Comparison sorts]]
[[Category:Articles with example Python (programming language) code]]