クイックソートは,情報I教員研修用教材第3章「コンピュータとプログラミング」の131ページに掲載されています.これを Picthon を使って書き換えてみました.ちなみに以前選択ソートをPicthonで書き換えたプログラムはこちらにあります.
def quicksort(a, start, end):
m = int((start+end)/2)
i = start
j = end
while(i<j):
while a[i] < a[m]:
i = i+1
draw(a, i, j)
while a[j] > a[m]:
j = j-1
draw(a, i, j)
if i>=j:
break
temp = a[i]
a[i] = a[j]
a[j] = temp
if i==m:
m = j
elif j==m:
m = i
i = i+1
j = j-1
draw(a, i, j)
if start < i-1:
quicksort(a, start, m-1)
if end > j+1:
quicksort(a, m+1, end)
def draw(a, i, j):
pic.CS()
pic.C()
pic.MW(-300,0)
for k in range(len(a)):
pic.SC(a[k] / 200)
pic.ST()
pic.MW(35, 0)
pic.SC(0)
pic.T("⇩", -325 + i * 35, -150, 50)
pic.T("⇩", -325 + j * 35, -150, 50)
pic.W(0.1)
a = [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
draw(a, -1, -1)
quicksort(a,0,len(a)-1)
実行例
