2.2. Bogosort

Bogosort (also known as Permutation sort or Stupid sort) is the brute-force approach to sorting.

It enumerates all permutations of the input until it finds the sorted version.

Fig. 2.2 Bogosort goes through all permutations of the input until it finds a sorted version.

The name comes from the word “bogus” because it is a bogus sorting algorithm.

There are many variants of bogosort. The difference between the two most common variants is that of determinism and randomness. The deterministic version enumerates all permutations until it encounters a sorted one whereas the randomized version permutes its input randomly. Here, we are discussing the deterministic version.

2.2.1. Psuedocode

The pseudocode for bogosort is as follows:

Algorithm 2.2 (Bogosort Algorithm)

Inputs A list \(L\) of length \(n\)

Output The permutation of \(L\) that is sorted i.e. \(L'\) such that \(L'[i] \leq L'[i+1]\) for all \(i\) from \(0\) to \(n-1\)

1. Compute all permutations of \(L\)

2. For each permutation \(P\) of \(L\):

   2.1. If \(P\) is sorted, return \(P\)

Note that computing all permutations of a given list is in itself a hard algorithmic problem. Here, we are assuming that we have a function that can compute all permutations of a given list.

2.2.2. Implementation

The following is an implementation of bogosort in Python:

import itertools

def is_sorted(arr):
    for i in range(len(arr) - 1):
        if arr[i] > arr[i + 1]:
            return False
    return True

def bogo_sort(arr):
    all_permutations = itertools.permutations(data)
    for permutation in all_permutations:
        if is_sorted(permutation):
            return permutation
    return None

Note that the above implementation uses the built-in itertools library to compute all permutations of the input list.

2.2.3. Analysis

Bogo Sort is extremely inefficient. It has an average runtime of \(O(n \times n!)\).

This is because the total number of permutations of an array of length \(n\) is \(n!\). Each permutation takes \(O(n)\) time to check if it is sorted. Therefore, the total runtime is \(O(n \times n!)\).

Space complexity is O(1) because the algorithm sorts the array in place, without allocating memory for any new list.