[解決済み】3値の中央値戦略

質問内容

クイックソートでピボット値を選択する3つの戦略のうち、中央値は何ですか？

ウェブで読んでいるのですが、具体的にどのようなものか分かりませんでした。また、ランダムなクイックソートよりどのように良いのでしょうか？

どのように解決するのですか？

3つの要素の中央値とは、配列の最初、真ん中、最後の要素を見て、その3つの要素の中央値をピボットとして選択することです。

3つの中央値の効果を最大限に引き出すには、次のことも重要です。 ソート これは、現在の反復処理でピボットとして選択されるものには影響しませんが、次の再帰呼び出しでピボットとして使用されるものに影響する可能性があり、いくつかの初期順序の悪い動作を制限するのに役立ちます（多くの場合、特に悪いと判明したものは、配列のハイエンドに最小の要素がある（またはローエンドに最大の要素がある）ことを除いてソートされている配列です）。例えば

ピボットをランダムに選ぶのに比べ

1. ある共通のケース（完全にソートされたデータ）が最適のままであることを保証します。
2. ワーストケースを与えるように操作することがより困難である。
3. PRNGは比較的低速であることが多い。

2点目は、もう少し説明が必要でしょう。もしあなたが明らかな( rand() 乱数発生器を使えば、誰かが簡単に（多くの場合、とにかく）悪いピボットを選び続けるように要素を配置することができます。これは、潜在的な攻撃者が入力したデータをソートしているウェブサーバのようなものにとって、深刻な懸念となり得ます。このような場合、あなたは 可能性 本当にランダムな種を使うか、rand()の代わりに自作のPRNGを入れるか、あるいは3のメディアンを使うかです。

一方、十分にランダムな生成器（例えば、ハードウェア生成器やカウンターモードでの暗号化など）を使用する場合は、おそらく より 3つの選択の中央値よりも悪いケースを強要することは困難です。同時に、そのレベルのランダム性を達成することは、一般的にそれ自身のかなりのオーバーヘッドを持つので、このケースで攻撃されることを本当に期待していない限り、おそらくそれは価値がありません（もしそうなら、少なくともマージソートやヒープソートのような、O（N log N）最悪の場合を保証する代替を検討する価値があるでしょう。