クイックソートの平均計算量はどれか？

📝 解説

クイックソートは「ピボット（基準値）を選び、それより小さいグループと大きいグループに分割する」操作を再帰的に繰り返す、分割統治法に基づくソートアルゴリズムです。図書館の本を整理するとき「まず著者名のア行か行以降かで2山に分け、各山をさらに細かく分ける」やり方と同じ発想です。この分割が毎回ほぼ均等に行われる場合、分割の深さがlog n層になり1層あたりn回の操作で済むため、平均計算量はO(n log n)になります。クイックソートはキャッシュ効率も良く定数係数が小さいため実際の動作も非常に高速で、C言語のqsort()やPythonのTimSortなど多くの言語の標準ライブラリに採用されています。ただしピボットの選び方が悪く毎回最小か最大が選ばれると分割が偏り最悪O(n²)になります。乱数や中央値でピボットを選ぶことで最悪ケースを回避するのが実用上の工夫です。「クイックソート平均＝O(n log n)、最悪＝O(n²)」をセットで覚えましょう！