4 ms·
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 shu
by ChristianMarks 13y ago
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)
print a
print turdsort(a)
shuffle(a)
print a
print turdsort(a)
- ChristianMarks 13y agoThere 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)