#クイックソートを実装する
最初に「26」を基準の数(ピボット)とする。
「26」より大きい物をLeftへ
「26」より小さい物をRightへセットする。
左と右に分けられるので
それぞれ分けられたリストを同様の処理をしていく。
Left[32, 65, 76, 43, 87, 59]
Right[13, 22, 14]
次にLeftがソーティングされますがピボットは先頭の「32」です。
これを繰り返すことで下の結果の通りになります。
QuickSort.py
data = [26,13,32,65,76,22,43,87,14,59]
def QuickSort(data):
if len(data) <= 1: # データが1個以下ならそのまま値を戻す
return data
# 基準となるデータ(ピボット)としてリストの先頭の値を使用
pivot = data[0]
left, right, same = [], [], 0 # 初期化(リスト、リスト、0)
for ii in data:
if ii > pivot:
left.append(ii) # ピボットより大きい場合、左側へセット
elif ii < pivot:
right.append(ii) # ピボットより小さい場合、右側へセット
else:
same += 1 # 同じ値は移動せず、数だけカウント
left = QuickSort(left) # 左側のソート
right = QuickSort(right) # 右側のソート
# ソート済みデータとピボットとを合わせて返す
return left + [pivot] * same + right
print(QuickSort(data))
# 結果
# [87, 76, 65, 59, 43, 32, 26, 22, 14, 13]
「分割統治法」っという言い方もあるようですが、小さい単位に分割を繰り返して処理を再帰的に繰り返します。
ピボットの選び方次第で処理は速くもなればいろいろあるようです。