クイックソートについて
概要
- 計算量
- 最悪値:
O(n^2) - 平均:
O(n log n) - 平均的にquick sortのほうがmerge sortより高速らしい
- 最悪値:
- 手順
- 基準となる一点を決める(ランダムでも先頭でも可)
- 基準より大きい値、小さい値、等しい値に分割する
- 大きい値のグループ、小さい値のグループを再帰でquick sortする
- 出力を合成
視覚的な説明
コード
import random
def qsort(arr):
# 基準のpivotよりも小さいグループ、同じグループ、大きいグループに分ける
lesser, equal, greater = [], [], []
if len(arr) <= 1:
return arr
pivot = random.choice(arr) # pivotを定義
for x in arr:
if x < pivot:
lesser.append(x)
elif x == pivot:
equal.append(x)
elif x > pivot:
greater.append(x)
return qsort(lesser) + equal + qsort(greater)
arr = [random.randint(0, 100) for _ in range(11)]
print(arr) # [50, 80, 84, 22, 9, 33, 49, 21, 87, 45, 55]
print(qsort(arr)) # [9, 21, 22, 33, 45, 49, 50, 55, 80, 84, 87]