256bitの殺人メニュー

インフラエンジニアだったソリューションアーキテクトなくわののブログ。こちらのBlogは個人の意見となっていて会社とは全く関係ありません。お約束です。[twitter:@kuwa_tw]めんどくさがりが重い腰を上げて何かをアウトプットすることにどれほどの意味があるのかを試してみたいブログでもある。

シェーカーソート

なんか自分シェーカーソートらしいので勉強がてら書いてみた。

#!/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)

結構簡単、やっぱり安定ソートのが条件が少なくて書きやすいね。


この後クイックソートを書こうとして挫折。
休みにでも書いてみよ。