ピボットを選び小さい値を左・大きい値を右へ分けるクイックソートを棒アニメーションで確認。平均O(n log n)でも逆順でO(n²)に落ちる理由を目撃できます。
アルゴリズム
配列
比較
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²)に悪化します — 「逆順」プリセットで確認できます。 ソート可視化