Bogosort

Time Complexity

Space Complexity

Overview

Do you understand the algorithm looking at the animation alone?

I guess not... because the animation shows just randomness, in a slightly less technical way.

But why randomness?

Because this is what Bogosort algorithm is!

It's an algorithm that simply takes and input, shuffles it and checks if the output is sorted. And there's no 'progress' in it.
In simple terms - finishing one iteration doesn't get you closer to a sorted output, like it would in most other algorithms.
Imagine it like sorting a deck of cards... by throwing them in the air and expecting them to fall on the ground in perfect order. It could happen and if you do it enough times, it may eventually happen but we can't be certain of it.

This leads to the weird and dramatic time complexity of O(∞) - meaning that there's no guarantee that we will get a sorted output even if we continue trying forever.
After all, if you throw a deck of cards in the air, you wouldn't really expect it to fall ordered on the ground, even if you throw it many times.
And that's the 'raw' or 'randomized' version of the algorithm.

To make it less absurd, there's an improvement over the algorithm flow in its 'deterministic' version.
It simply means that we find and exhaust all possible permutations of the given input rather than use complete randomness. In this case, we have 'progress' and we do check for already sorted elements so that we can know what to skip in the next iteration. And if you remember the permutation symbol from school - it leads to time complexity of O(n x n!).

It's interesting to know though, that there are scenarios in which Bogosort could actually perform on par with some other 'normal' algorithms. And that's because of it's best case scenario, which is O(n). This is the case in which we deal with an already sorted input. For instance - you are being handed an ordered deck of cards and you just need to check it to verify if it's ordered by looking at each card (hence the 'n' to indicate checking of each element). If the deck is ordered, there's no need to throw it in the air at all and you just stop.

And if you are now confused and wondering what are the use cases of this algorithm? They are none!

It shouldn't be used in any real world scenarios. Rather, it's more of a theoretical algorithm that is used for teaching purposes, fun or to demonstrate your computer science knowledge in front of other people :)

Now I think you know why this algorithm is also called Permutation Sort, Stupid Sort or Bogus Sort!

Code

In simple terms, Bogosort's randomized version could be expressed with the following pseudocode:
while !sorted(input)
shuffle(input)

Be careful if you execute these code examples! Given the nature of the algorithm and the amount of time it could take, it could lead to freezing or crashing the environment you run it on, especially with larger input.

import random
 
def bogosort(arr):
    while any(arr[i] > arr[i + 1] for i in range(len(arr) - 1)):
        random.shuffle(arr)
    return arr
 
my_list = [5,6,2,3,4,1]
sorted_list = bogosort(my_list)
print(sorted_list)
 

function bogosort(arr) {
    while (arr.some((value, index) => index > 0 && value < arr[index - 1])) {
        arr.sort(() => Math.random() - 0.5);
    }
    return arr;
}
 
const input = [5,6,2,3,4,1];
const sortedArray = bogosort(input);
console.log(sortedArray);
 
 

import java.util.Arrays;
import java.util.Random;
 
public class Bogosort {
    private static boolean isSorted(int[] arr) {
        return Arrays.stream(arr).noneMatch(i -> i > arr[0]);
    }
 
    private static void bogosort(int[] arr) {
        Random rand = new Random();
        while (isSorted(arr)) {
            for (int i = 0; i < arr.length; i++) {
                int randomIndexToSwap = rand.nextInt(arr.length);
                int temp = arr[randomIndexToSwap];
                arr[randomIndexToSwap] = arr[i];
                arr[i] = temp;
            }
        }
    }
 
    public static void main(String[] args) {
        int[] myArray = {5,6,2,3,4,1};
        bogosort(myArray);
        System.out.println(Arrays.toString(myArray));
    }
}
 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
 
bool isSorted(int arr[], int size) {
    for (int i = 1; i < size; i++) {
        if (arr[i] < arr[i - 1]) {
            return false;
        }
    }
    return true;
}
 
void bogosort(int arr[], int size) {
    srand(time(NULL));
    while (!isSorted(arr, size)) {
        for (int i = 0; i < size; i++) {
            int randomIndexToSwap = rand() % size;
            int temp = arr[randomIndexToSwap];
            arr[randomIndexToSwap] = arr[i];
            arr[i] = temp;
        }
    }
}
 
int main() {
    int myArray[] = {5,6,2,3,4,1};
    int size = sizeof(myArray) / sizeof(myArray[0]);
    bogosort(myArray, size);
    for (int i = 0; i < size; i++) {
        printf("%d ", myArray[i]);
    }
    printf("\n");
    return 0;
}
 
 
 

<?php
 
    function isSorted($arr) {
        $count = count($arr);
        for ($i = 1; $i < $count; $i++) {
            if ($arr[$i] < $arr[$i - 1]) {
                return false;
            }
        }
        return true;
    }
 
    function bogosort($arr) {
        while (!isSorted($arr)) {
            shuffle($arr);
        }
        return $arr;
    }
 
    $anotherArray = array(5,6,2,3,4,1);
    $sortedAnotherArray = bogosort($anotherArray);
    print_r($sortedAnotherArray);
 
?>