ピボットに基づいたパーティション配列

Question

ピボットに基づいてパーティションを分割する簡単な実装を書いています。簡単にするために、配列内の最初の要素をピボット要素とします。以下は、私は以下の配列のために今

public static void partitionOnPivot(int[] a , int lo , int hi) 
{ 

    int pivot = lo; 

    while (lo < hi) 
    { 
     while(a[lo] <= a[pivot]) lo++; 
     while(a[hi] > a[pivot]) hi--; 

     if(lo < hi) //we are already done with these cases 
     { 
      ArrayUtil.swap(a, lo++, hi--); 
     } 
    } 

    ArrayUtil.swap(a, pivot, lo); 

} 

を書いたコード、一点で

{26,84,98,45} 

が交換され、この点26で、インデックス1

に立つ、両方loとhiです84となり、出力は{84, 26, 98, 45}になります。 26は放置されていたはずです。

私はかなりの時間をかけて進歩なしにいくつかの変更を行っています。このコーナーケースはどうやって処理しますか？プログラムにバグはありますか？

Answer 1

使用ループ

ArrayUtil.swap(a, pivot, hi); 

Answer 2

ArrayUtil.swap(a, lo++, hi--);ながら、外の最後にこの文では、あなたの望ましくない行動がで忍び寄るされた場合、私はきっとあります。 ++はポストインクリメントであるため、ピボットでハイ要素をスワップしてから、ピボットをインクリメントします。

Answer 3

"loとhiの両方がインデックス1になります" - > WRONG あなたが書いたプログラムから、loはインデックス1に、hiはインデックス0になることは明らかです。条件はスキップされ、ふたつのインデックスで値をスワップ最後の行は

if(lo < hi) //THE FOLLOWING STATEMENT WILL BE SKIPPED 
    { 
     ArrayUtil.swap(a, lo++, hi--); 
    } 

が実行される結果として得られるアレイは{84、26、98、45}であろう。もしそうであれば、以下のそれはまさにあなたが得ているものです。あなたは

while(a[lo] <= a[pivot]) lo++; 
while(a[hi] > a[pivot]) hi--; 

は、他の人が私はインクリメントとデクリメントを考える

ArrayUtil.swap(a, lo++, hi--); 

PS

ArrayUtil.swap(a, lo, hi); 

に変更してみてくださいを指摘してきたとしても

while(a[lo + 1] <= a[pivot]) lo++; 
while(a[hi - 1] > a[pivot]) hi--; 

になり、次の変更を行う必要があります演算子は悪の。 1つは実際にpost/preの動作について注意を払う必要があります。できるだけそれらを避けてください。