用語集
クイックソートくいっくそーと
ピボットを基準に分割していく高速ソート。平均 O(N log N)、最悪 O(N²)。
ピボットを基準に分割していく高速ソート。平均 O(N log N)、最悪 O(N²)。
クイックソート（Quick Sort）は、ピボット（基準値）を 1 つ選び、それより小さい要素と大きい要素に分割して、それぞれを 再帰（再帰）で同様にソートする分割統治型のアルゴリズムです。
| 観点 | クイックソート |
|---|---|
| 平均計算量 | |
| 最悪計算量 | |
| 仕組み | ピボットで分割→再帰 |
| 特徴 | 平均的に最速級・追加メモリ少 |
たとえばピボットに中央付近の値を選ぶと、左右がほぼ均等に分かれて効率よくソートできます。平均では実用最速級ですが、すでに整列済みのデータでピボット選択が偏ると最悪 になります。多くの標準ライブラリで採用される定番ソートです。
試験では 「ピボットで分割」「平均・最悪」と、マージソート との違い（安定性・メモリ）が問われます。