Bogo Sort in Python

This post deals with one of the most¬†inefficient¬†sorting algorithms in programming – the Bogo Sort in Python! The name itself is derived from the “Bogus Sort”

The sorting algorithm has almost no application. However, it is often used to highlight how an incorrectly implemented algorithm can go haywire and use up unnecessary time and space. It highlights the importance of efficiency in a solution.

Prerequisites: Must know to generate all possible permutations of an array and random module in Python.

What is Bogo Sort?

The sorting method basically produces all possible permutations of a given list and checks if it sorted or not. It is as simple as that and clearly takes a whole lot of time for execution, even for small arrays. It is simply a trial and error method.

There are, however, two ways of implementing bogo sort. One is to generate at least the permutations logically and pass it on to check if it is sorted. The other is even worse! We randomly shuffle elements of the array and check if it is sorted. Ridiculous, isn’t it? It is like throwing all the numbers out there, picking them up randomly and hoping they’re sorted.

We discuss both implementations here, just to show how inefficient a solution can be!

Method 1 to implement bogo sort in Python

As mentioned earlier, the method generates all permutations and check if it is in sorted order. If yes, the list is returned.

Consider the following program,

from itertools import permutations

def bogo_sort(arr):
    for k in permutations(arr):
        for m in range(len(k)-1):
            if k[m]<=k[m+1]:
                pass
            else:
                break
        else:    
            return k

print bogo_sort([2,5,3,74,44,12,1,67,99,1221])        

The program takes about 17 seconds to complete execution just for an array size of 11. Note that sometimes, by chance, one of the first few iterations may return the sorted array. Only under such situations, the method is fast and it is a pure chance (of course, it does depend on the order in which the array elements are passed to the function as the permutation function has a certain algorithm to give all possible permutations!)

bogo sort in Python

Method 2 – Bogo sort in Python

Here, we take random numbers from the array, put them into a new array and check if it is sorted!

Consider the following program,

import random

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

def bogo_sort(arr):
    while(True):
        for m in range(len(arr)-1):
            if arr[m]<=arr[m+1]:
                pass
            else:
                break
        else:    
            return arr
        arr = reorder(arr)

print bogo_sort([2,5,3,74,44,22,17,28,99])

 

It took about 18 seconds for an array of length 9.

output of bogo sort

 

Hence we understand the importance of efficient solutions to problems!!!

Feel free to leave behind any sort of feedback, suggestions, doubts below

Learn:

Leave a Reply

Your email address will not be published. Required fields are marked *