基本情報技術者 一問一答｜A 第52問

解説

クイックソートは、基準値（ピボット）を選んで要素を「ピボットより小さいグループ」と「大きいグループ」に分割し、各グループに同じ処理を再帰的に適用する分割統治法のソートである。分割の深さが平均してlog n段程度、各段での比較が合計n回程度になるため、平均計算量はO(n log n)となる。ただしピボットの選び方が悪く分割が極端に偏ると、最悪O(n²)に劣化する点に注意が必要である。O(n²)はバブルソートなど単純ソートの計算量（クイックソートでは最悪時のみ）であり、O(n)やO(log n)は比較に基づくソート全体の計算量としては達成できない。基本情報技術者試験では「ピボットで分割し再帰的に整列」という手順の説明と、平均O(n log n)・最悪O(n²)の区別が頻出ポイントである。