algodat sort

sort.py

import random

def sort(a, feedback=False):
  lower_limit = 0
  upper_limit = len(a) - 1
  steps = 0

  while(lower_limit != upper_limit ):
    i = lower_limit
    while i < upper_limit - 1:
      if a[i] > a[i+1]:
        a[i], a[i + 1] = a[i + 1], a[i]
        if upper_limit == i+1 and upper_limit < len(a) - 1:
          upper_limit += 1
        if lower_limit == i and lower_limit > 0:
          lower_limit -= 1
      elif lower_limit + 1 == i:
        lower_limit += 1
      i += 1
      steps += 1

    i = upper_limit - 1
    while i >= lower_limit:
      if a[i] > a[i+1]:
        a[i], a[i + 1] = a[i + 1], a[i]
        if upper_limit == i+1 and upper_limit < len(a) - 1:
          upper_limit += 1
        if lower_limit == i and lower_limit > 0:
          lower_limit -= 1
      elif upper_limit - 1 == i:
        upper_limit -= 1
      i -= 1
      steps += 1
  if feedback:
    print "list of length %d took %d steps" % (len(a), steps)
        
print "running tests:",
for i in range(10000):
  a = [random.randint(0, 100) for x in range(20)]
  b = a[:]
  a.sort()
  sort(b)
  if a != b:
    print "  error with list %s == %s" % (a, b)
print " finished"
print

unsorted = [random.randint(0, 100) for x in range(20)]
print "Sort this list: %s" % unsorted
sort(unsorted, True)
print unsorted
print 

unsorted.reverse()
print "Sort reversed list: %s" % unsorted
sort(unsorted, True)
print unsorted