algorithm - クイック ソート アルゴリズムでのピボットの選択

Question

クイックソートを学んでいます。ピボット値が不均衡なパーティションを実行すると、クイック ソートのパフォーマンスが低下することを私は知っています。そのため、最初の要素または最後の要素は適切な選択ではありません。リストがほとんど並べ替えられている場合、パーティションのバランスが崩れるからです。

検索したところ、2つのオプションが見つかりました：

1 つは、低(最低のインデックス) とアップ(最高のインデックス)の間でピボットをランダムに選択することでした。これは安全なオプションのようですが、乱数ジェネレーターは時間がかかります。

2 つ目は、すべての要素の中央値を取ることです。このオプションはコストがかかるため、最初、最後、および中間要素の中央値をピボット要素として使用できます。

クイックソートで最も効率的であることが判明した方法はどれですか?.ピボット要素を選択するために利用できる他の方法はありますか?

Answer 1

はい、配列がソートされているか、ほぼソートされていることを心配している場合は、お勧めのように、適切なピボットを選択するためにより多くの努力を続けて適用できますが、データがソートされていない場合はアルゴリズムの速度が低下します。The Algorithm Design Manual のSkienna は、ピボット選択について適切な議論を行っており、クイックソートを適用する前に配列をランダム化することもできると示唆していますが、それほど心配している場合は、別のソート アルゴリズムの方がパフォーマンスが優れていると思います。

クイックソートで最も効率的であることが証明されている方法はどれですか?

ここでの重要なポイントは、データのパフォーマンス測定を実行することです。

Answer 2

最悪のシナリオが本当に心配な場合は、各再帰呼び出しでサブ配列をランダム化してください。これにより、最悪のケースから保護されます。