Bogo Sort Algorithm

Bogosort is a purely random sorting algorithm. It is inefficient because it is probablistic in nature. The algorithm is simple. Randoming shuffling the array until they are in order. The algorithm can be described below in Python.

def bogo(x):
    while not inorder(x):
        shuffle(x)
    return x

The best case is that the array is already sorted, and in this case, no swap is carried out but there will be elements comparisons. The running time complexity grows exponentially as the number of elements to sort increases. However, one of its advantages is that the space complexity is nearly because no additional space needs to be allocated for this algorithm.

The average swaps for Bogosort is

The entire python script can be downloaded at [github]

#!/usr/bin/env python
"""
    https://helloacm.com
    BogoSort.py
    Bogo Sorting Algorithm
    30/May/2012
"""

from random import *
from time import *

seed()
x = []
for i in range(0, 10):
    x.append(randint(0, 100))

def inorder(x):
    i = 0
    j = len(x)
    while i + 1 < j:
        if x[i] > x[i + 1]:
            return False
        i += 1
    return True

def bogo(x):
    while not inorder(x):
        shuffle(x)
    return x

start = time()
print "Before: ", x
x = bogo(x)
print "After: ", x
print "%.2f seconds" % (time() - start)

The rough time to sort 10 elements is 5 seconds on Win7, Intel i7, 8GB RAM

Before:  [58, 35, 55, 24, 4, 31, 39, 30, 22, 85]
After:  [4, 22, 24, 30, 31, 35, 39, 55, 58, 85]
5.44 seconds

–EOF (The Ultimate Computing & Technology Blog) —