クイックソート再帰

Question

私は、毎回ピボットとして最も左の要素を使用するクイックソートを正常に実装しました。私は中間要素を使用し、いくつかの複雑な結果を持ってクイックソートを実装しようとしてきました。私は、クイックソートを再帰的に呼び出す例を取り組んできましたが、何らかの条件でコールをラップすることなく、自分自身を最初に呼び出したときにスタックされてしまいます。

私が使用したサンプルでパーティションを最初に呼び出すと、配列が正しくパーティション化され、最後に近づくにつれて、最初の要素の2つが何度も何度も入れ替えられます。

私が試みている戦略では、リストから中間の要素をピボットとして選択し、配列の終わりに配置してインデックスをスワップします。そのパスが完了したら、分割された配列の間にピボットを配置します。 2回のパスの後にはうまくいくように見えますが、私が言及したように、早期に立ち往生し、2番目のパーティションをソートするコールに決して行きません。

いかなるnudgesをいただければ幸いです - あなたは何を見送る場合、私はまた、グルーヴィーで働いていた（そして、できればそれがすべての問題の原因ではないが、私は元の配列が

あるこの

ためダックタイピングを避け

[100, 305, 2, 2002, 18, 99, 211, 30, 50, 1000, 403, 4, 400, 77]

、スタックオーバーフローが到達したときアレイは

[2, 4, 18, 30, 50, 99, 77, 100, 211, 1000, 403, 305, 400, 2002]

であります

class OtherQuickSort { 

static void sort(int[] array){ 

    quickSort(array, 0, array.length - 1) 

} 

static void quickSort(int[] array, int first, int last){ 
     int pivotIndex = partition(array, first, last) 

     quickSort(array, first, pivotIndex - 1) 
     quickSort(array, pivotIndex, last) 
} 

static int partition(int[] array, int first, int last){ 
    int pivotIndex = (first + last)/2 
    int pivotValue = array[pivotIndex] 

    swapIndices(array, pivotIndex, last) 

    int indexFromRight = last - 1 
    int indexFromLeft = first 

    while(indexFromLeft <= indexFromRight){ 
     while(array[indexFromLeft] < pivotValue){ 
      indexFromLeft++ 
     } 
     while(array[indexFromRight] > pivotValue){ 
      indexFromRight-- 
     } 

     if(indexFromLeft <= indexFromRight) { 
      swapIndices(array, indexFromLeft, indexFromRight) 
      indexFromLeft++ 
      indexFromRight-- 
     } 
    } 

    swapIndices(array, indexFromLeft, last) 

    indexFromLeft 
} 

static void swapIndices(int[] array, int left, int right){ 
    int leftValue = array[left] 
    array[left] = array[right] 
    array[right] = leftValue 
} 
} 

Answer 1

quickSortメソッドを更新する必要があります。 pivotIndexの値は既にソートされた位置にあるため、再度渡す必要はありません。

static void quickSort(int[] array, int first, int last){ 
    if(last > first){ 
     int pivotIndex = partition(array, first, last); 

     quickSort(array, first, pivotIndex-1); 
     quickSort(array, pivotIndex+1, last); 
    } 
}