News for hackers. Stuff that matters.
Re:Bogo-bogosort by ChristianMarks on Saturday December 28, 2013 @11:25PM (#6978361)
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)
Re:Bogo-bogosort by ChristianMarks on Sunday December 29, 2013 @01:05AM (#6978618)
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)