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
Top comments (0)