Bogosort

In computer science, bogosort<ref name="Fun07"/><ref name="KSFS">Template:Citation</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 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.<ref>Template:Cite web</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">Template:Citation.</ref> 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:

<math>P(\text{at least one success}) = 1 - (P(\text{failure in one trial}))^n</math>

Here, 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 n! possible permutations is sorted, the probability of success in a single trial is <math>1/n!</math>. Thus, the probability of obtaining a sorted list within k shuffles is:

<math>P(\text{sorted within } k \text{ shuffles}) = 1 - \left(1 - \tfrac{1}{n!}\right)^k</math>

This framing highlights the extreme inefficiency of Bogosort: even for modest values of n, the probability of success remains vanishingly small unless k is astronomically large.<ref>Template:Cite web</ref><ref>Template:Cite journal</ref>

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:<syntaxhighlight lang="c" line="1">

1. include <stdio.h>
2. include <stdlib.h>
3. 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:

<syntaxhighlight lang="python"> import random

1. 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

1. 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

1. 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)]

1. 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 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

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 Template:Math, and the expected number of swaps in the average case equals Template:Math.<ref name="Fun07">Template:Citation.</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 Template:Math, 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.

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