なんか自分シェーカーソートらしいので勉強がてら書いてみた。
#!/usr/bin/python # INIT import random from datetime import * randlen = 10000 randlst = [] # SUB routin def printlst(lst): print lst def createList(lst): lst = [] random.seed() print random.random(), 'n' for i in xrange(randlen): tmp = random.randint(1, 100) lst.append(tmp) return lst def shakerSort(lst): topidx = 0 btmidx = len(lst) - 1 lastswap = 0 while topidx < btmidx: for i in xrange(topidx, btmidx): if lst[i] > lst[i + 1]: lst[i+1], lst[i] = lst[i], lst[i+1] lastswap = i btmidx = lastswap for i in xrange(btmidx, topidx, -1): if lst[i] < lst[i - 1]: lst[i-1], lst[i] = lst[i], lst[i-1] lastswap = i topidx = lastswap # MAIN print "ShakerSort" randlst = createList(randlst) printlst(randlst) shakerSort(randlst) printlst(randlst)
結構簡単、やっぱり安定ソートのが条件が少なくて書きやすいね。
この後クイックソートを書こうとして挫折。
休みにでも書いてみよ。