クイックソートアルゴリズムは、宿題のためにStackOverflowExceptionが

Question

を投げ、私はクイックソートアルゴリズムの実装を作成し、いくつかのランダムな順序で100kの番号のリストをソートするためにこれを使用する必要があります。

は、割り当ての最初の部分で、Iは、ピボット要素として配列の最初の項目を使用しなければなりません。これはソートされたリストを返します。ただし、割り当ての2番目の部分では、最後の項目をピボットとして使用する必要があり、結果としてStackOverflowExceptionが発生します。 8レコードの小さなコレクションで試してみると、正常に動作します。私は自分のコードを見てきましたが、私はどこで間違いをしているのか分かりません。どんな助けでも大歓迎です。私のコードは次の通りです：

public class QuickSort { 

    private QuickSortStrategyEnum quickSortStrategy; 

    public QuickSort(QuickSortStrategyEnum quickSortStrategy) { 

     this.quickSortStrategy = quickSortStrategy; 
    } 

    public List<Integer> sortIntegerArray(List<Integer> arrayList, int left, int right) { 

     if (left >= right) { 
      return arrayList; 
     } 

     int i = partition(arrayList, left, right); 

     if (i <= right) { 

      int pivotNew = partition(arrayList, i, right); 
      int pivotIndex = arrayList.indexOf(pivotNew); 

      arrayList = sortIntegerArray(arrayList, left , pivotIndex - 1); 
      arrayList = sortIntegerArray(arrayList, pivotIndex + 1, right); 
     } 

     return arrayList; 
    } 

    private int partition(List<Integer> arrayList, int left, int right) { 

     int pivot = getPivot(arrayList, left, right); 
     int i = left + 1; 

     for (int j = i; j <= right; j++) { 

      if (arrayList.get(j) < pivot) { 

       Collections.swap(arrayList, j, i); 
       i++; 
      } 
     } 

     Collections.swap(arrayList, left, i - 1); 
     return i; 
    } 

    private int getPivot(List<Integer> arrayList, int left, int right) { 

     int pivot = 0; 

     switch (quickSortStrategy) { 

      case FIRST: 
      pivot = arrayList.get(left); 
      break; 

      case LAST: 
      pivot = arrayList.get(right); 
      break; 
     } 
     return pivot; 
    } 

} 

Answer 1

David Harkness氏によれば、パーティションロジックには問題があります。これを試してみてください：（デイヴィッド・ハークネスが指すものを取り除いた後）

private int partition(List<Integer> arrayList, int left, int right) { 

    int pivot = getPivot(arrayList, left, right); 
    int i = left - 1; 

    for (int j = left; j < right; j++) { 
     if (arrayList.get(j) <= pivot) { 
      i++; 
      Collections.swap(arrayList, j, i); 
     } 
    } 

    Collections.swap(arrayList, i+1, right); 
    return i+1; 
} 

ピボットが最後の要素であるとき、それはケースのために動作します。最初の要素ではありません。

読むには、Eclipseに挨拶、その後、紙、ドライラン物事うちに作業を理解する擬似コードを記述します。物事を急いではいけません。

Answer 2

ヒント：right == left + 1の場合はどうなりますか？何partitionリターンで

int pivotNew = partition(arrayList, i, right); 
int pivotIndex = arrayList.indexOf(pivotNew); 

ルックを、あなたはその結果を使用してどのようにそれを比較：

Answer 3

この2行は、魚に見えます。