このMedian of mediansアプローチは、型分割アルゴリズムで非常に人気がありquicksort、配列を均一に分割するなど、かなり優れたピボットを生成します。その論理はウィキペディアで次のように示されています。
選択されたピボットは、中央値のリストにある要素の半分未満と半分より大きい両方です。これは、各半分で約n / 10要素（1/2 *（n / 5））です。これらの各要素は中央値5であり、他の2つの要素より少なく、ブロックの外側にある他の2つの要素より大きくなります。したがって、ピボットは、ブロックの外側の3（n / 10）要素未満であり、ブロックの外側の別の3（n / 10）要素よりも大きくなります。したがって、選択された中央値は、要素を30％/ 70％から70％/ 30％の間のどこかに分割します。これにより、アルゴリズムの最悪の場合の線形動作が保証されます。
誰かが私のためにそれを少し明快に説明できますか？論理を理解するのが難しいと感じています。
次の一連の数字について考えてみてください。
5 2 6 3 1
これらの数値の中央値はです3。今、あなたが数を持っているnなら、もしn > 3、それは上記の数の少なくとも半分よりも大きいです。の場合n < 3、上記の数値の少なくとも半分よりも小さくなります。
それがアイデアです。つまり、5つの数値のセットごとに、それらの中央値を取得します。今、あなたはn / 5数字を持っています。これは明らかです。
ここで、これらの数値の中央値を取得すると（中央値と呼びますm）、それらの半分よりも大きく、残りの半分よりも小さくなります（中央値の定義による）。言い換えると、mはn / 10数値（それ自体が小さな5要素グループの中央値でした）よりも大きく、別のn / 10数値（これも小さな5要素グループの中央値でした）よりも大きくなります。
上記の例では、中央値がでkあり、m > kがである場合、m他の2つの数値よりも大きいことがわかりました（それ自体はよりも小さかったk）。mこれは、中央値よりも大きい5つの要素グループのそれぞれについて、m他の2つの数値よりも大きいことを意味します。これにより、これらの小さな5つの要素グループのそれぞれで少なくとも3つの数値（2つの数値+中央値自体）が作成されます。これらは。n / 10よりも小さくなりmます。したがって、m少なくとも3n/10数値よりも大きくなります。
要素数の同様のロジックは、mよりも大きくなります。