クイックソートピボットの選択

Question

私はピボットが3つの数字、ボトム、ミドル、およびトップの中央値になることを読んだ。しかし、それはオーバーフローを生成する可能性がありますか？中央値が配列のサイズより大きな値を返すとどうなりますか？ この選択肢は、配列の値が配列のサイズよりも長くなることができないと仮定していると仮定します。 私はピボットが本当に何であるか混乱していると思います。

Answer 1

ピボットは他の値と比較する値にすぎません。低い値は左に、右に行くほど高くなります。ピボットは、配列内の既存の値のいずれかを取ることによって選択できます。配列が完全にソートされていない場合は、どの値を選択するかは関係ありません。多少ソートされている場合は、配列の中央から値を選択する必要があります。

更新：より良いピボットの選択肢は、配列の3つの値の中央値（中、下、上、または3つのランダムな位置など）を選択することです。一部の人々は5値の中央値を取ることを提唱している。クイックソートの最悪の場合のパフォーマンスは、ピボットがアレイ内の最小値または最大値に近い場合に発生し、この方法は発生したことに対して防御することを意図しています。これは特定の種類のデータの最適化に過ぎません。必要ではありません。