はじめに
クイックソートの Python サンプルコードを紹介します。
実用として最もよく使われるソート手法です。
サンプルコード
サンプルコードの紹介です。
def quicksort(xs, start, end):
print(xs, start, end)
if end - start <= 1:
return xs
pos = partition(xs, start, end)
quicksort(xs, start, pos)
quicksort(xs, pos, end)
def partition(xs, start, end):
i = (start + end) // 2
pivot = xs[i]
p = start
q = end - 1
while True:
while xs[p] < pivot and p < i:
p += 1
while xs[q] >= pivot and i < q:
q -= 1
if p == i and q == i:
break
xs[p], xs[q] = xs[q], xs[p]
if p == i:
i = q
elif q == i:
i = p
return i
if __name__ == '__main__':
xs = [2, 8, 7, 1, 3, 5, 6, 4]
print('initial:', xs)
quicksort(xs, 0, len(xs))
print('sorted :', xs)❯ python3 quicksort.py
initial: [2, 8, 7, 1, 3, 5, 6, 4]
[2, 8, 7, 1, 3, 5, 6, 4] 0 8
[2, 1, 3, 7, 8, 5, 6, 4] 0 2
[1, 2, 3, 7, 8, 5, 6, 4] 0 0
[1, 2, 3, 7, 8, 5, 6, 4] 0 2
[1, 2, 3, 7, 8, 5, 6, 4] 0 1
[1, 2, 3, 7, 8, 5, 6, 4] 1 2
[1, 2, 3, 7, 8, 5, 6, 4] 2 8
[1, 2, 3, 4, 5, 8, 6, 7] 2 4
[1, 2, 3, 4, 5, 8, 6, 7] 2 3
[1, 2, 3, 4, 5, 8, 6, 7] 3 4
[1, 2, 3, 4, 5, 8, 6, 7] 4 8
[1, 2, 3, 4, 5, 6, 8, 7] 4 5
[1, 2, 3, 4, 5, 6, 8, 7] 5 8
[1, 2, 3, 4, 5, 6, 7, 8] 5 7
[1, 2, 3, 4, 5, 6, 7, 8] 5 6
[1, 2, 3, 4, 5, 6, 7, 8] 6 7
[1, 2, 3, 4, 5, 6, 7, 8] 7 8
sorted : [1, 2, 3, 4, 5, 6, 7, 8]サンプルコード（副作用なし）
もうひとつ副作用なし版サンプルコードの紹介です。
インプットのリストを更新しません。
その代わり処理効率が少し劣ります。
def quicksort(xs):
print(xs)
if len(xs) <= 1:
return xs
pivot = xs[0]
return (
quicksort([x for x in xs if x < pivot])
+ [x for x in xs if x == pivot]
+ quicksort([x for x in xs if pivot < x])
)
if __name__ == '__main__':
xs = [2, 8, 7, 1, 3, 5, 6, 4]
print('initial:', xs)
ys = quicksort(xs)
print('sorted :', ys)❯ python3 quicksort_fn.py
initial: [2, 8, 7, 1, 3, 5, 6, 4]
[2, 8, 7, 1, 3, 5, 6, 4]
[1]
[8, 7, 3, 5, 6, 4]
[7, 3, 5, 6, 4]
[3, 5, 6, 4]
[]
[5, 6, 4]
[4]
[6]
[]
[]
sorted : [1, 2, 3, 4, 5, 6, 7, 8]おしまい！