Q&A
[余計なお世話]
誤: ピポット
正: ピボット(pivot)
現在クイックソートを勉強している学生です。
クイックソートのピボットの決め方について質問があります。
最良と最悪が下記二つであることはわかりました
理想は配列の中央値で均等に分割すること
ー＞要素数が多い場合そもそも中央値を求めるのに時間がかかるから×
計算量n^2となる最悪な選び方
ー＞配列の最大値or最小値を常に選び続ける
自分なりに調べた結果下記の三つのやり方がよくつかわれることがわかりました
①ランダム
②複数サンプルとり、その中央値
③先頭二つの要素をとり、大きい方を選ぶ（同じ場合は次の要素と比較）
個人的には②>③>①な気がするのですがどうでしょうか
ちなみに、私が考えるそれぞれのメリット・考え方は
①②も③も最小値や最大値を引く可能性があるなら余計な計算など瀬津にランダムでいいという考え
②複数サンプルのうちの中央値を選択するので、最小値や、最大値を選択する可能性が低い、かつ③より中央に近い値を取りやすい
③配列の要素がほぼすべて同じでない限り最大値や最小値を引く可能性が低い
それぞれ、ほかに方法があったりするのでしょうか？
解答よろしくお願いします。
ご指摘ありがとうございます！
ピボットの選び方とは違いますが、再帰の深さによってアルゴリズムを変えることで最悪計算量を O(n log n) に抑える工夫があるようです。
https://ja.wikipedia.org/wiki/%E3%82%A4%E3%83%B3%E3%83%88%E3%83%AD%E3%82%BD%E3%83%BC%E3%83%88
回答ありがとうございます！
回答1件
0
ベストアンサー
たぶんお手本に相応しい実装:標準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つ集めてその中の中央値"みたいなことを繰り返してるポいです。
投稿2020/07/16 00:11
編集2020/07/16 06:26総合スコア16612
解答ありがとうございます！
[3.2]よりも[3.1]のほうが要素数に関係なくより良いピボットを選択できるような気がするのですが、どうでしょうか
それこそ例に挙げてもらったような"3値の中央値を3つ集めてその中の中央値"なら計算量もそれほど大きくないように感じるのですがどうでしょうか
よろしければ回答よろしくお願いします
知らんがな。コード読んだらそうなってた。(ざっくりとだから誤読もあるかも)
あなたも読んでみるといいよ。
ありがとうございます！
読んでみます！
あなたの回答
tips
プレビュー
