Skip to content

Instantly share code, notes, and snippets.

@Mononofu
Created March 18, 2012 20:09
Show Gist options
  • Save Mononofu/2080783 to your computer and use it in GitHub Desktop.
Save Mononofu/2080783 to your computer and use it in GitHub Desktop.
algodat sort
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment