I have a soft spot in my head for turdsort , which attempts to optimize over bogosort , but ends up being no better. #!/usr/bin/python from random import shuffle def turdsort(a): def turds(a): n = 0 for i in xrange(len(a)-1): if a[i] > a[i+1]: n += 1 return n count = 1 n = len(a) t = turds(a) while n > 0: while t >= n: shuffle(a) t = turds(a) count += 1 n = t return count if __name__ == '__main__': a = range(10) prin…
There is also the slightly less pointless ordersort, which works only on permutations. The complexity of ordersort is given by the Landau function. It is more efficient than bogosort, however.
#!/usr/bin/python
def gcd(a,b):
while b:
a, b = b, a % b
return a
def order(a):
"""compute the order of the permutation a"""
lcm = 1
for i in range(len(a)):
j = a[i]
while j > i:
j = a[j]
if j == i: # i is a cycle leader
j = a[j] # get next element of cycle
cyc = 1; # the cycle has length at least 1
while j != i: # the cycle hasn't closed
cyc += 1
j = a[j]
lcm = (lcm/gcd(lcm,cyc))*cyc
return lcm
def ordersort(a):
ord = order(a)
print ord
b = range(len(a))
while ord > 0:
b = map((lambda i: a[i]), b)
ord -= 1
return b
if __name__ == '__main__':
from random import shuffle
a = range(50);
shuffle(a)
print a, ordersort(a)