クイックソートの平均計算量として適切なものはどれか。

📝 解説

クイックソートは「ピボット（基準値）を選び、ピボットより小さい要素と大きい要素の2グループに分割する」操作を再帰的に繰り返す分割統治法による整列アルゴリズムです。図書館で本を整理するとき「500番台を境に前後に分け、さらにそれぞれを250番と750番で分け…」と繰り返す方法がまさにクイックソートの発想です。平均的なケースでは毎回ほぼ均等に分割されるため、O(n log n)という非常に効率的な計算量を達成します。これはn件のデータをlog nの深さで分割し、各レベルでn回の処理が必要という構造によるものです。ただし最悪ケース（既にほぼ整列済みのデータで毎回最大・最小をピボットに選ぶと）はO(n2)に悪化します。ランダムなピボット選択や「3つの中央値」を選ぶ方法でこのリスクを低減できます。実用上はキャッシュ効率が高くインプレース（追加メモリが少ない）なため、多くの標準ライブラリで採用されています。誤答の「O(n)」はハッシュ探索や計数ソートなど特殊ケース、「O(n2)」はバブルソート・選択ソートの平均計算量、「O(log n)」は二分探索の計算量です。「クイックソート＝平均O(n log n)・最悪O(n2)・分割統治法」と覚えましょう！