algorithm - ランダムに選択されたピボットの利点

Question

クイックソートでは、さまざまな方法でピボット値を選択できます。ピボット値をランダムに選択することもその1つです。ピボット値をランダムに選択すると、O（n ^ 2）になる可能性が最小限に抑えられるということです。誰かがそれがどのように起こるのか説明できますか？不利な点はありますか？

Answer 1

ランダムピックと非ランダムピックの両方で、期待値がすべての可能な入力（順列）で平均化されている場合、期待実行時間がTheta（n * log（n））であるアルゴリズムが生成されます。

実際には、すべての入力順列が同じように発生する可能性があるわけではありません。特に、pick-firstがTheta（n ^ 2）の複雑さを与える場合、ソートされた配列またはほぼソートされた配列を取得することがよくあります。その上、ピッキングアルゴリズムが決定論的である場合、攻撃者は厄介な順列を作成してアルゴリズムを2次式にし、サービス拒否を実現する可能性があります。

ピボットとしてランダムな要素を選択すると、これらのランダムでないケースを防ぐことができます。

Answer 2

ランダムピボットで予想される実行時間はTheta（n logn）であるという数学的証明があります。

wikiページにはそのセクションがあります。