質問: 情報系学生です クイックソートではpivotの決め方が非常に重要だと思うのですが、それぞれにどのようなメリットがあるのでしょうか? 1配列から3つ選び、その中の中央値をpivotとする 2配列の先頭2要素を比べ大きい方をpivotとする 3ランダム 41を繰り返し、1で得られた中央値候補の中央値をpivotとする 正直優先順位的には 4>1>3>2だと思うのですがどうでしょうか 私が考えるメリット 1最小値や最大値を避けられる可能性が高く中央値に近い値が選択できる可能性がある 2よくわかりません 3結局1でも4でも最大値や最小値を選ぶ可能性があるなら余計な計算などせずにランダムでいい?? 41の最大値・最小値を取る確率を下げ、中央値に近い値を取れる可能性がさらに高くなる(計算量は少し増える)
回答: まず、中央値や最大値を選ぶ方法とランダムに選ぶ方法では、決定的なアルゴリズムになるか確率的なアルゴリズムになるかという大きな違いがあります。クイックソートはピボットの選び方を間違えると停止しないアルゴリズムです。このためピボットをランダムに選んでしまうとソートが停止しない可能性も残ります。またそれ以外にも、最近の計算機において「ランダムな値を選ぶ」というのは中央値や最大値を選ぶのに比べるとコストが高い計算であることにも注意が必要です。 たとえば日本語版 Wikipedia に載っているクイックソートのアルゴリズムにおいては、配列の要素たちの唯一の最小値を毎回ピボットに選んでしまうと停止しません。「先頭ふたつの最大値をピボットにする方法」や「3 つ選んでその中央値をピボットにする方法」はソートを停止させる保証を得るために必要な手間です。 更に、クイックソートではなるべく配列の要素たちの中央値をピボットに選べると要素間で比較する回数の平均値を減らせます。配列から 3 要素選んで(たとえば先頭の 3 つを選んで)その中央値をピボットとするやり方は、これを期待しています。実際平均的には「先頭ふたつの最大値」方式より高速になる......はずです。 最後に再帰的に中央値を求めるやり方についてです。たとえば次のような実装を考えてみましょう:全体を三分割し、それぞれについて「3 つ要素を選んで中央値をとる」操作をした結果を m1, m2, m3 とし、更にこれら 3 つの中央値となる要素をピボットとする。これに似たやり方が C 言語の `qsort` 関数の実装を追った論文 "Engineering a Sort Function" (Bentley & Mcilroy. 1993. リンク) で検討されており、当時の実験では単に「3 つ選んで中央値をとる」方法よりも時間計算量が小さい、と主張しています。 個人的にはこのあたりの優劣は実際に実装して計測してみるのが一番だと思っています。このあたりをチューニングし始めると、そもそも中央値の近似計算にどの程度実時間がかかるのか、や、配列の要素の入れ替えだとかいった処理にどの程度実時間がかかるのか、などといった要素が絡んでくるため、どのような実装が速いのかを決める概算が簡単にはやりづらくなります。たとえば最近の CPU はかなりうまく分岐予測をするので......とか、配列が無茶苦茶長いとキャッシュに乗るかどうかが問題になってくるので......、とかいった事情が無視できなくなってきます。このため最終的には実験をして速度を確かめるのがてっとりばやいです。 以上をまとめると:一般論としては「先頭ふたつの最大値」や「ランダム」よりも「(何かしらの規則にしたがって選ばれた)3 つの要素の中央値」が平均的には速くなりそうですが、実際のところは実装や計算機によるので、最終的には実験してみてください。 補足:たとえば英語版 Wikipedia の Quicksort のページにも pivot selection について幾らか書かれているので参考になると思います。ソートの高速化という意味で関連する、イントロソートや dual-pivot quicksort についても触れられています。