From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Data structureArray
Worst-case performanceUnbounded (randomized version),[1] O((n+1)!) (deterministic version)
Best-case performanceO(n)[1]
Average performanceO((n+1)!)[1]
Worst-case space complexityO(n)

In computer science, bogosort[1][2] (also known as permutation sort, stupid sort,[3] slowsort,[4] shotgun sort, or monkey sort) is a highly inefficient 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 useful for sorting, but may be used for educational purposes, to contrast it with more efficient algorithms.

Two versions of this algorithm exist: a deterministic version that enumerates all permutations until it hits a sorted one,[2][4] and a randomized version that randomly permutes its input. 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. Its name is a portmanteau of the words bogus and sort.[5]

Description of the algorithm[edit]

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

while not isInOrder(deck):

Here is the above pseudocode re-written in Python 3:

import random

def is_sorted(data) -> bool:
    """Determine whether the data is sorted."""
    for i in range(len(data) - 1):
        if data[i] > data[i + 1]:
            return False
    return True

def bogosort(data) -> List:
    """Shuffle data until sorted."""
    while not is_sorted(data):
    return data

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

Here is an example with shuffle in Standard ML:

 val _ = load "Random";
 load "Int";
 val rng = Random.newgen ();

 fun select (y::xs, 0) = (y, xs)
   | select (x::xs, i) = let val (y, xs') = select (xs, i-1) in (y, x::xs') end
   | select (_, i) = raise Fail ("Short by " ^ Int.toString i ^ " elements.");

 (* Recreates a list in random order by removing elements in random positions *)
 fun shuffle xs =
    let fun rtake [] _ = []
          | rtake ys max =
             let val (y, ys') = select (ys, Random.range (0, max) rng)
             in y :: rtake ys' (max-1)
    in rtake xs (length xs) end;

 fun bogosort xs comp = 
 let fun isSorted (x::y::xs) comp = comp(x,y) <> GREATER andalso isSorted (y::xs) comp
       | isSorted _ comp = true;
     val a = ref xs;
 in while(not(isSorted (!a) comp)) do (
  a := shuffle (!a)
  ); (!a) end;

Running time and termination[edit]

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 , and the expected number of swaps in the average case equals .[1] 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 , and no swaps at all are carried out.[1]

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[edit]

is a sorting algorithm introduced in the 2011 Google Code Jam.[6] 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.
is an algorithm that was designed not to succeed before the heat death of the universe on any sizable list. It works by recursively calling itself with smaller and smaller copies of the beginning of the list to see if they are sorted. The best 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, copies back if not, and returns. Otherwise, it reshuffles the current copy of the list and goes back to its recursive check.[7]
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 a bozosort is more difficult, but some estimates are found in H. Gruber's analysis of "perversely awful" randomized sorting algorithms.[1] O(n!) is found to be the expected average case.
is a pessimal sorting algorithm that is guaranteed to complete in finite time; however, there is no computable limit to the inefficiency of the sorting algorithm, and therefore it is more pessimal than the other algorithms described herein. The algorithm is based on a bad sorting algorithm, . The badsort algorithm accepts two parameters: , which is the list to be sorted, and , which is a recursion depth. At recursion level , merely uses a common sorting algorithm, such as bubblesort, to sort its inputs and return the sorted list. That is to say, . Therefore, badsort's time complexity is if . However, for any , first generates , the list of all permutations of . Then, calculates , and returns the first element of the sorted . To make truly pessimal, may be assigned to the value of a computable increasing function such as (e.g. , where is Ackermann's function). Ergo, to sort a list arbitrarily badly, you would execute , where = number of elements in . The resulting algorithm has complexity , where = factorial of iterated times. This algorithm can be made as inefficient as we wish by picking a fast enough growing function .[8]

Analysis of runtime[edit]

Here is some Python code to efficiently test the average complexity of Bogosort.

Experimental runtime of bogosort
#!/usr/bin/env python3.6

import sys
import time
import random
from multiprocessing import Process, Queue

import numpy as np
import matplotlib.pyplot as plt
from scipy.special import factorial
from tqdm import tqdm


def is_sorted(some_list):
    """Determine whether the specified list is sorted."""
    for x, y in zip(some_list[:-1], some_list[1:]):
        if x > y:
            return False
    return True

class Sorter(Process):
    def __init__(self, array, output: Queue, counts: Queue, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.array = array
        self.length = len(array)
        self.output = output
        self.count = 0
        self.counts = counts

    def run(self) -> None:
        while True:
            if self.output.empty():
                new_list = random.sample(self.array, k=len(self.array))
                self.count += self.length  # To check all items
                if is_sorted(new_list):

def run_trial(list_len):
    trials = {"time": [], "cycles": []}
    for _ in tqdm(range(TRIAL_COUNT)):
        start_time = time.time()
        array = random.sample(list(range(list_len)), k=list_len)

        workers = []
        output = Queue()
        counts = Queue()
        for _ in range(WORKER_COUNT):
            w = Sorter(array, output, counts)

        _result = output.get()

        total_count = 0
        for _ in range(WORKER_COUNT):
            total_count += counts.get()

        for _ in range(WORKER_COUNT):

        for w in workers:

        end_time = time.time()
        trials["time"].append(end_time - start_time)

    return trials

def plot_chart(list_lengths, results) -> None:
    # Init chart
    fig, axarr = plt.subplots(2, 1, figsize=(8, 6))

    # Average time graph
    # Plot runtime to the graph
    for i, (length, trial) in enumerate(zip(list_lengths, results)):
        trial_time = np.ones(TRIAL_COUNT) * length
        axarr[0].plot(trial_time, np.log(trial["time"]), "rx", alpha=0.4)

    # Plot average result
    avg_result = [np.log(sum(t["time"]) / len(t["time"])) for t in results]
    axarr[0].plot(list_lengths, avg_result, label="Average Result")

    # Chart labels
    axarr[0].set_xlabel("Length of Initial List")
    axarr[0].set_ylabel("Average Time Elapsed - ln(seconds)")

    # Average operation graph
    # Plot cycles to graph
    for i, (length, trial) in enumerate(zip(list_lengths, results)):
        trial_ops = np.ones(TRIAL_COUNT) * length
        axarr[1].plot(trial_ops, np.log(trial["cycles"]), "rx", alpha=0.4)

    # Plot average result
    avg_result = [np.log(sum(t["cycles"]) / len(t["cycles"])) for t in results]
    axarr[1].plot(list_lengths, avg_result, label="Average Result")

    # Plot n . n!
    n_dot = np.log([n * factorial(n) for n in list_lengths])
    axarr[1].plot(list_lengths, n_dot, label=r"$n \cdot n!$",)

    # chart labels
    axarr[1].set_xlabel("Length of Initial List")
    axarr[1].set_ylabel("Average Time Elapsed - ln(Operations)")

    # Headings and set layout
    fig.suptitle("Parallel Bogosort")

    # Save the plot
def main():
    list_lengths = range(2, 10)  # Random length for the unsorted lists
    trial_results = []

    # Run trials and add results to array
    for list_len in list_lengths:
        trial_info = run_trial(list_len)

    # Plot info to chart and save as PNG
    plot_chart(list_lengths, trial_results)

if __name__ == "__main__":

See also[edit]


  1. ^ a b c d e f g Gruber, H.; Holzer, M.; Ruepp, O., "Sorting the slow way: an analysis of perversely awful randomized sorting algorithms", 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007 (PDF), Lecture Notes in Computer Science, 4475, Springer-Verlag, pp. 183–197, doi:10.1007/978-3-540-72914-3_17.
  2. ^ a b Kiselyov, Oleg; Shan, Chung-chieh; Friedman, Daniel P.; Sabry, Amr (2005), "Backtracking, interleaving, and terminating monad transformers: (functional pearl)", Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05) (PDF), SIGPLAN Notices, pp. 192–203, doi:10.1145/1086365.1086390, archived from the original (PDF) on 26 March 2012, retrieved 22 June 2011
  3. ^ E. S. Raymond. "bogo-sort". The New Hacker’s Dictionary. MIT Press, 1996.
  4. ^ a b Naish, Lee (1986), "Negation and quantifiers in NU-Prolog", Proceedings of the Third International Conference on Logic Programming, Lecture Notes in Computer Science, 225, Springer-Verlag, pp. 624–634, doi:10.1007/3-540-16492-8_111.
  5. ^ "Bogosort". The Jargon File 4.4.8. 2003. Retrieved 11 April 2013.
  6. ^ Google Code Jam 2011, Qualification Rounds, Problem D
  7. ^ Bogobogosort
  8. ^ Lerma, Miguel A. (2014). "How inefficient can a sort algorithm be?". arXiv:1406.1077 [cs.DS].

External links[edit]