DEV Community

loading...
Cover image for Bogo sort algorithm

Bogo sort algorithm

Aya Bouchiha
Full stack web developer
Updated on ・2 min read

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Have an amazing day!

References and useful resources

#day_21

Discussion (0)