クイックソートホアアレイアレイパーティショニング

Question

ホアレパーティションアルゴリズムが常にアレイを2つの右部分に分割する理由を理解しようとしています。以下のコードでは、私は

int partition(int[] arr, int leftIndex, int rightIndex) { 
    int pivot = arr[(leftIndex + rightIndex)/2]; 

    while (leftIndex <= rightIndex) { 
    while (arr[leftIndex] < pivot) leftIndex++; 
    while (arr[rightIndex] > pivot) rightIndex--; 

    // If all numbers at right places, than leftIndex and rightIndex 
    // could point at same array element index 
    // So it's means partion done. 
    // We should return leftIndex + 1 cause 
    // rightIndex points at the last element of the left sub array 

    if (leftIndex == rightIndex) return leftIndex + 1; 

    if (leftIndex < rightIndex) { 
     swap(arr, leftIndex, rightIndex); 
     leftIndex++; 
     rightIndex--; 
    } 
    } 

    //But here the tricky thing: Why does this "if case" never execute? 
    if (leftIndex - 1 > rightIndex) 
    System.out.println("leftIndex - 1 > rightIndex"); 

    return leftIndex; 
} 

（詳細についてはコメントを参照してください）私にはそれがより明確にするためにHoare algorithmを拡張そこで質問です：それは機能を分割するために配列を渡すことは可能ですので、以下の行が実行されます？それを実行するためには

if (leftIndex - 1 > rightIndex) 
    System.out.println("leftIndex - 1 > rightIndex");? 

Answer 1

、我々はleftIndexで機能を起動すると仮定すると、leftIndexは、少なくともrightIndex + 2でなければならないであろう、そしてそれはちょうど起こることはできません< = rightIndex：これら二つのループで

：

while (arr[leftIndex] < pivot) leftIndex++; 
while (arr[rightIndex] > pivot) rightIndex--; 

インデックスが互いに交差することはできません - ない早く場合、彼らはピボットのいずれかの側で停止します。

これが事実であるならば、我々は機能を残して：

if (leftIndex == rightIndex) return leftIndex + 1; 

ので、残っている唯一のものがある：

if (leftIndex < rightIndex) { 
    swap(arr, leftIndex, rightIndex); 
    leftIndex++; 
    rightIndex--; 
} 

彼らは限り近い方でもすることができ（leftIndex == rightIndex - 1 ）、実行後はleftIndex == rightIndex + 1になります。そして、我々はまだ2の違いを得ていませんでした。