Python Program for BogoSort or Permutation Sort

BogoSort, also known as Permutation Sort, Stupid Sort, Slow Sort, Shotgun Sort, or Monkey Sort, is a highly inefficient sorting algorithm based on the generate-and-test paradigm. It repeatedly shuffles the elements of the list until it becomes sorted.

Algorithm:

Start with an unsorted list of elements.
Repeatedly shuffle the list randomly.
After each shuffle, check if the list is sorted.
Stop when the list becomes sorted.

Implementation of BogoSort

Python

import random

def bogo_sort(arr):
    while True:
        sorted_flag = True
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                sorted_flag = False
                break
        
        if sorted_flag:
            break  

        n = len(arr)
        for i in range(n):
            r = random.randint(0, n - 1)
            arr[i], arr[r] = arr[r], arr[i]

arr = [3, 2, 4, 1, 0, 5]
bogo_sort(arr)
print("Sorted array:", *arr)

Output

Sorted array: 0 1 2 3 4 5

Explanation:

while True: keeps the process running until the list becomes sorted.
The inner loop checks if each element is ≤ the next.
If not sorted, it shuffles the array using random swaps.
The loop stops once the array becomes sorted.

BogoSort - Using Built-in Functions

A shorter version can be written using Python’s built-in sorted() and random.shuffle():