質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

Q&A

解決済

1回答

3539閲覧

クイックソートのpivotの決め方について

konnitiha2

総合スコア30

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

1グッド

2クリップ

投稿2020/07/15 11:30

編集2020/07/15 23:45

現在クイックソートを勉強している学生です。

クイックソートのピボットの決め方について質問があります。
最良と最悪が下記二つであることはわかりました

理想は配列の中央値で均等に分割すること
ー>要素数が多い場合そもそも中央値を求めるのに時間がかかるから×

計算量n^2となる最悪な選び方
ー>配列の最大値or最小値を常に選び続ける

自分なりに調べた結果下記の三つのやり方がよくつかわれることがわかりました

①ランダム
②複数サンプルとり、その中央値
③先頭二つの要素をとり、大きい方を選ぶ(同じ場合は次の要素と比較)

個人的には②>③>①な気がするのですがどうでしょうか

ちなみに、私が考えるそれぞれのメリット・考え方は
①②も③も最小値や最大値を引く可能性があるなら余計な計算など瀬津にランダムでいいという考え
②複数サンプルのうちの中央値を選択するので、最小値や、最大値を選択する可能性が低い、かつ③より中央に近い値を取りやすい
③配列の要素がほぼすべて同じでない限り最大値や最小値を引く可能性が低い

それぞれ、ほかに方法があったりするのでしょうか?
解答よろしくお願いします。

DrqYuto👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

episteme

2020/07/15 12:38

[余計なお世話] 誤: ピポット 正: ピボット(pivot)
konnitiha2

2020/07/15 12:39

ご指摘ありがとうございます!
konnitiha2

2020/07/16 06:23

回答ありがとうございます!
guest

回答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
episteme

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

konnitiha2

2020/07/16 06:27

解答ありがとうございます! [3.2]よりも[3.1]のほうが要素数に関係なくより良いピボットを選択できるような気がするのですが、どうでしょうか それこそ例に挙げてもらったような"3値の中央値を3つ集めてその中の中央値"なら計算量もそれほど大きくないように感じるのですがどうでしょうか よろしければ回答よろしくお願いします
episteme

2020/07/16 06:31 編集

知らんがな。コード読んだらそうなってた。(ざっくりとだから誤読もあるかも) あなたも読んでみるといいよ。
konnitiha2

2020/07/16 06:58

ありがとうございます! 読んでみます!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問