Bogo sort algorithm

Hi, today, I'm going to talk about ridiculous sorting algorithms which are called Bogo sort

Definition of Bogo sort

Bogo sort: called also stupid sort, slow sort, monkey sort is a type of sorting algorithms, it works by shuffling randomly array elements until the array is sorted.

Time & Space complexity

Time complexity:

Best case: O(n)
Average case: O(n!)
Worst case: infinte ( because there is no guarantee that a randome suffling will ever produce a sorted array )

The space complexity of Bogo sort is O(1)

Implementation of Bogo sort using Python

for getting a random integer to shuffle the array we need to import randint from the random module

from random import randint

Shuffle function

def shuffle(arr: list):
    for i in range(len(arr)):
        randomInt = randint(0, len(arr) - 1)
        arr[randomInt], arr[i] = arr[i], arr[randomInt]

isSorted function

we should implement a function that checks if the array is sorted, if the function returned True, It means the array is sorted and we need to break the loop, else (returned False) we'll shuffle it again until the array will be sorted.

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

Bogo sort

this function shuffles the array randomly until it is sorted.

def BogoSort(arr: list) -> list:
    # while the array is not sorted
    while not isSorted(arr):
        shuffle(arr)
    # if the array is sorted
    return arr

Final Code

from random import randint

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

def shuffle(arr: list)  :
    for i in range(len(arr)):
        randomInt = randint(0, len(arr) - 1)
        arr[randomInt], arr[i] = arr[i], arr[randomInt]

def BogoSort(arr: list) -> list:
    while not isSorted(arr):
        shuffle(arr)
    return arr

Have an amazing day!

References and useful resources

#day_21

Blog

Aya Bouchiha