質問: 現在クイックソートを勉強している学生です。 クイックソートのピボットの決め方について質問があります。 最良と最悪が下記二つであることはわかりました 理想は配列の中央値で均等に分割すること ー>要素数が多い場合そもそも中央値を求めるのに時間がかかるから× 計算量n^2となる最悪な選び方 ー>配列の最大値or最小値を常に選び続ける 自分なりに調べた結果下記の三つのやり方がよくつかわれることがわかりました 1ランダム 2複数サンプルとり、その中央値 3先頭二つの要素をとり、大きい方を選ぶ(同じ場合は次の要素と比較) 個人的には2>3>1な気がするのですがどうでしょうか ちなみに、私が考えるそれぞれのメリット・考え方は 12も3も最小値や最大値を引く可能性があるなら余計な計算など瀬津にランダムでいいという考え 2複数サンプルのうちの中央値を選択するので、最小値や、最大値を選択する可能性が低い、かつ3より中央に近い値を取りやすい 3配列の要素がほぼすべて同じでない限り最大値や最小値を引く可能性が低い それぞれ、ほかに方法があったりするのでしょうか? 解答よろしくお願いします。
回答: たぶんお手本に相応しい実装:標準C++ライブラリのstd::sortを覗いてみました(Visual C++) [1] 要素数が小さいとき(32以下) insertion-sortに切り替え [2] 分割がある程度進んだらheap-sortに切り替え [3] さもなくば先頭/中央/末尾を元にpivot選択してquick-sort [3.1] 要素数が小さいなら先頭~末尾間の中央値 [3.2] それ以上なら先頭/中央/末尾の3つの中央値 ざっくりこんな↑かんじ。intro-sortと同じ戦略かと(てかまんまintro-sortかと)。 スピード命ですから * 要素数が小さいときにはquick-sortはややこしすぎる * 中央値の算出に時間かけるわけにはいかん ので、上記のようなアルゴリズムなのでしょう。 ※ [3.1] 要素数が小さいなら先頭~末尾間の中央値 これもマジメに求めるんじゃなく、"3値の中央値を3つ集めてその中の中央値"みたいなことを繰り返してるポいです。