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) —
loading...
Last Post: Codeforces: A. Funky Numbers
Next Post: __name__ in Python
in that sounds of sorting program, the highlighted ones in bogosort are what? I had thought they were just the values being compared, but there are multiple higlighted elements…. anyways that’s a C# program so maybe it’s different, but I’m just looking for something similar.
好奇葩的算法。。