クイックソートとピボット選択とは？
クイックソートとピボット選択とは、基準値（ピボット）より小さい要素と大きい要素に分割し、それぞれを再帰的に整列する分割統治型の整列法。平均O(n log n)で定数倍が小さく実用上最速級だが、分割が偏ると再帰が深くなり最悪O(n²)まで悪化する。
くいっくそーととぴぼっとせんたく
クイックソートとピボット選択の意味
基準値（ピボット）より小さい要素と大きい要素に分割し、それぞれを再帰的に整列する分割統治型の整列法。平均O(n log n)で定数倍が小さく実用上最速級だが、分割が偏ると再帰が深くなり最悪O(n²)まで悪化する。
クイックソートとピボット選択の具体例
既に昇順に並んだ配列で先頭を常にピボットにすると、毎回1個と残り全部に分割され最悪計算量になる。実装では中央値3つの中央（median-of-three）やランダム選択を使い、偏りが続かないようにするのが定石。
クイックソートとピボット選択は試験でどう引っ掛けられる？
平均と最悪の計算量が異なる代表例で、「クイックソートは常にO(n log n)」は誤り。また追加配列を必要としない反面、再帰のスタックを使うため厳密には完全な定位置整列ではなく、安定ソートでもない。
クイックソートとピボット選択と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。