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)