Funny sorting algorithm

Published on
Funny sorting algorithm

Bogosort

The most useless and stupid sorting algorithm

How it works?

Well, let’s say that the basic operation of this algorithm is really very simple, this checks an array asking each time if it is sorted, if it is not, the array is randomized and the cycle repeats.

Unlike all the other algorithms this one doesn’t make any sense.

Time of execution

This sorting algorithm is probabilistic in nature. If all elements to be sorted are different, the complexity is: O(n × n!)

The reason why the algorithm almost certainly arrives at a conclusion is explained by the tireless monkey theorem: with each attempt there is a probability of getting the sort right, so given an unlimited number of attempts, it should eventually succeed.

Almost certainly, here, it is a precise mathematical term.

Implementation

This is a simple Python3 implement of this kind of algo

import random

def bogo_sort(a):
    i = 0
    while not is_sorted(a):
        print(f"Iteration {i}: {a}")
        random.shuffle(a)
        i += 1
    return a

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

def main():
    a = []
    l = input("Insert array length: ")
    for i in range(int(l)):
        a.append(random.randint(0, 1000))
    bogo_sort(a)
    print(f"Final iteration: {a}")

if __name__ == "__main__":
    main()

Visualize Execution

Authors