クイックソートの平均的な計算量（オーダー）はどれか。

📝 解説

クイックソートは「基準値（ピボット）を選び、それより小さいグループと大きいグループに分割する」操作を再帰的に繰り返す分割統治法のアルゴリズムです。図書館で本を整理するとき、まず「500番台より前か後か」で大別し、各グループ内でさらに細分化する方法と同じ発想です。平均計算量はO(n log n)と高速で、C言語やPythonなど多くの標準ライブラリで採用されています。ただし最悪ケース（整列済みデータでピボットが端になる場合）はO(n²)に落ちるため、ランダムなピボット選択で改善するのが一般的です。誤答の「O(n)」はハッシュ探索など特殊ケース、「O(n²)」はバブルソートや選択ソート、「O(log n)」は二分探索の計算量です！