クイックソートとは？

詳細解説

クイックソート（Quicksort）は、配列から「ピボット」と呼ぶ基準値を選び、ピボットより小さい要素を左、大きい要素を右に分割する操作（パーティション）を再帰的に繰り返すことで整列するアルゴリズムです。分割統治（Divide and Conquer）パラダイムの典型例です。平均計算量はO(n log n)であり、実装次第では定数係数が小さいためC++標準ライブラリ（std::sort）などで広く採用されています。一方、ピボット選択が悪い場合（例：すでにソート済みの配列に対して先頭要素をピボットにする）は分割が偏りO(n²)になる最悪ケースがあります。この問題はランダムピボット選択や「3点メジアン法（先頭・中央・末尾の中央値をピボット）」で緩和できます。FE試験では「クイックソートの手順のトレース」「ピボット選択と分割の回数の関係」「マージソートとの比較（安定性・メモリ使用量）」が頻出です。クイックソートは**不安定ソート**（同値要素の順序が変わりうる）であることも重要な違いです。

FE試験での出題ポイント

• 1平均O(n log n)、最悪O(n²)（ピボット選択が最悪の場合）
• 2不安定ソート（同値要素の相対順序が変わる場合あり）
• 3ランダムピボット/3点メジアン法で最悪ケースを回避
• 4マージソートとの比較：クイック（空間O(log n)）vs マージ（安定・空間O(n)）

関連用語