大きいサイズ（100,000）の配列でQuickSortを実行すると、Java - StackOverflowErrorが発生する

Question

System.nanoTimeでQuickSortの効率を測定する課題を処理しています。私は他の配列サイズ（例えば100,1000,10,000）で動作するコードを持っていますが、サイズが100,000の配列を使用してメソッドを試行すると、StackOverflowErrorを受け取ります。また、InsertionSortとBubbleSortのために、これが100,000という大きさの配列に対応していることに注意してください。

目標はnanoTimeにランタイムを測定する、アレイと、第5次の100回の測定、クイックソートを介して105回実行することです。

まず、所定のサイズのランダムなint配列を作成します。次に、そのint配列をクローニングし、目的のソートメソッド（この例ではQuickSort）にクローンを渡します。最後に、QuickSortを使用して必要な回数実行する方法を作成しました。私は間違って何をやっている

public static void quickSort(int[] list) { 
quickSort(list, 0, list.length - 1); 
    } 

private static void quickSort(int[] list, int first, int last) { 
if (last > first) { 
    int pivotIndex = partition(list, first, last); 
    quickSort(list, first, pivotIndex - 1); 
    quickSort(list, pivotIndex + 1, last); 
} 
    } 

    private static int partition(int[] list, int first, int last) { 
int pivot = list[first]; // Choose the first element as the pivot 
int low = first + 1; // Index for forward search 
int high = last; // Index for backward search 

while (high > low) { 
    // Search forward from left 
    while (low <= high && list[low] <= pivot) 
    low++; 

    // Search backward from right 
    while (low <= high && list[high] > pivot) 
    high--; 

    // Swap two elements in the list 
    if (high > low) { 
    int temp = list[high]; 
    list[high] = list[low]; 
    list[low] = temp; 
    } 
} 

while (high > first && list[high] >= pivot) 
    high--; 

// Swap pivot with list[high] 
if (pivot > list[high]) { 
    list[first] = list[high]; 
    list[high] = pivot; 
    return high; 
} 
else { 
    return first; 
} 

次のようにインストラクターが提供するクイックソートのコードがある

public static void quickSort(int[] unsortedArray, int size, int max) { 
    long averageTime = 0; 

    for (int i = 0; i < RUN_TIMES; i++) { 
     if (i < 5) { 
      QuickSort.quickSort(unsortedArray); 
     } else { 
      long startTime = System.nanoTime(); 
      QuickSort.quickSort(unsortedArray); 
      long stopTime = System.nanoTime(); 
      long runTime = stopTime - startTime; 
      averageTime = averageTime + runTime; 
     } 
    } 

    System.out.println("Quicksort time for size " + size + 
      " and max " + max + ": " + averageTime/DIVISOR); 
} 

RUN_TIMESが105に設定され、除数が100に設定されている次のような方法がありますか？最終的には、NetBeansを新しいMacBook Proで使用しています。ちょうど私がすべてを共有したことを確かめたかった。どんな助けでも大歓迎です！

UPDATE：これはアレイを生成するために使用されるコードである：

private static int[] createArray(int size, int maxValue) { 
    int arraySize = size; 
    /* 
     Create array of variable size 
     Random int 1 - 999 
    */ 
    // Constructor for random and variable declaration 
    Random random = new Random(); 
    int x; 

    // Constructor for ArrayList<Integer> 
    ArrayList<Integer> tempArrayList = new ArrayList<>(); 

    // While loop used to create ArrayList w/100 unique values 
    while (tempArrayList.size() < arraySize) { 
     // Creates int value between 1 and 999 
     x = random.nextInt(maxValue) + 1; 

     // Checks if generated value already exists within ArrayList 
     if(!tempArrayList.contains(x)) { 
      // Add to ArrayList 
      //System.out.println("Added: " + x); 

      tempArrayList.add(x); 
     } else { 
      // Do nothing 
     } // end if - else 
    } // end while loop 

    // Convert ArrayList<Integer> to int[] 
    int[] arrayList = tempArrayList.stream().mapToInt(i -> i).toArray(); 

    return arrayList; 
} // end createArray method 

Answer 1

ショートバージョン：あなたのリストがソートされ、QSがソートされたリストの再帰の多くを必要とします。

QuickSortは、ピボットの選択（最初の項目）でリストがソートされたときに達成される最悪の場合の時間複雑度がO(n)の再帰的アルゴリズムです。代わりに、クイックソートのソートは、すなわち、それは入力配列を変更するので、それは、最初の反復の後、ある

。

最初の繰り返しの後、そのアレイ上のQuickSortには、n回帰、または100000が必要です。それは多いです。より良いソートアルゴリズム、または再帰を使用しないアルゴリズムを考えてみるか、再帰なしで再記述することを検討してください。

Answer 2

あなたはそれにそのスタックを所定の大きなデータセットを、所与その後、スタックに重い圧力をかける再帰アルゴリズムを、符号化されています圧力は問題の大きさの2乗に比例するので、なぜスタックオーバーフローが発生するのかについての謎はありません。あなたのアルゴリズムをループとして再コード化し、スタックに多量のごみを残さないでください。