quicksort - QuickSort での Media-of-3 パーティショニング

Question

median-of-3 パーティショニングでクイックソートを理解しようとしていました。配列の最初、中間、および最後の要素の中央値を見つけた後、一般的な方法は、中央値を配列の最後から 2 番目の要素 (n-1 番目のインデックス) と交換することです。私たちがそれを行う特定の理由はありますか？

Answer 1

その理由は、アルゴリズムが中央値を見つけるだけでなく、低、中、高の要素もソートするためです。3 つの順列の後、a[middle]<=a[high] であることがわかります。したがって、a[high] はピボット以上であるため、high の前に要素を分割するだけで済みます。

例を見てみましょう: 低 = 0、中 = 4、高 = 8。あなたの配列は次のようなものです：

lowerOrEqualToPivot XXX ピボット XXX greaterOrEqualToPivot

中央を高と交換する場合は、8 つの要素を括弧で区切る必要があります。

[ lowerOrEqualToPivot XXX greaterOrEqualToPivot XXX ] ピボット

middle を high-1 と入れ替えると、7 つの要素だけを分割する必要があります。

[ lowerOrEqualToPivot XXXXXX ] ピボットのより大きなOrEqualToPivot

ところで、最初の行にバグがあります:

int middle = (低 + 高) / 2; //間違った int middle = ( 低 + 高 ) >>> 1; //正しい

その理由は、(low + high) が Integer.MAX_VALUE より大きい場合、オーバーフローが発生し、中間が負の数になるためです。2 行目は常に肯定的な結果をもたらします。