クイックソート (Quick Sort)

ピボットを選び小さい値を左・大きい値を右へ分けるクイックソートを棒アニメーションで確認。平均O(n log n)でも逆順でO(n²)に落ちる理由を目撃できます。

アルゴリズム

配列

サイズ48
比較中交換/書込ピボット/基準読み整列確定
速度50×

比較

0

交換/書込

0

ステップ

0/467

読み

0

補助メモリ

0

再帰の深さ

1/1

速度を落として「1ステップ」で疑似コードのハイライトと棒の色を見比べてみてください。

疑似コード

quickSort(lo, hi)

pivot ← a[hi]

for j ← lo to hi−1

if a[j] ≤ pivot: a[i++] ↔ a[j]

a[i] ↔ a[hi] // 피벗 확정

quickSort(lo,i−1) quickSort(i+1,hi)

計算量

最良O(n log n)
平均O(n log n)
最悪O(n²)
空間O(log n)
安定×

クイックソートは基準値(ピボット)を1つ選び、小さい値を左・大きい値を右へ集める分割を繰り返します。紫が現在のピボットで、分割が終わるたびに最終位置が確定します。

ピボットが毎回中央付近を切れば深さlog nで平均O(n log n)、キャッシュ効率も良く実用最速クラスです。ただし逆順配列で末尾をピボットにするとO(n²)に悪化します — 「逆順」プリセットで確認できます。 ソート可視化

よくある質問

最悪O(n²)なのに標準ソートなのはなぜ?
ランダム・中央値ピボットで最悪ケースをほぼ消せるうえ、平均速度とキャッシュ効率が他のO(n log n)より優れるからです。
安定ソートですか?
いいえ。遠くの要素同士を交換するため同値の順序が崩れ得ます。

他のアルゴリズム