Java - StackOverflowError при выполнении QuickSort с массивом большого размера (100 000)

Question

Работа над назначением, измеряющим эффективность QuickSort в System.nanoTime. У меня есть код, который работает для других размеров массива (например, 100; 1000; 10 000), однако, когда я пытаюсь использовать метод с массивом размером 100 000, я получаю StackOverflowError. Также хорошо отметить, что у меня есть эта работа и массив размером 100 000 для InsertionSort и BubbleSort.

Цель состоит в том, чтобы запустить QuickSort 105 раз, измеряя 100 раз после первых 5, с массивом, измеряющим время выполнения в nanoTime.

Во-первых, я создаю случайный массив int заданного размера. Затем я клонирую этот массив int и передаю клон в нужный метод сортировки (QuickSort в этом случае). Наконец, я создал метод для запуска через необходимое количество раз с помощью QuickSort. Метод заключается в следующем:

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. Инструктор поставляемыми 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; 
} 

Что я делаю неправильно? Одна последняя мысль, я использую 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

Краткая версия: Ваш список отсортирован, а для сортировки списков требуется много рекурсии.

QuickSort - это рекурсивный алгоритм с наихудшей временной сложностью O(n), который достигается для вашего выбора стержня (первый элемент), когда список сортируется.

Какой он, после первой итерации, потому что QuickSort сортирует на месте, то есть изменяет входной массив.

После вашей первой итерации QuickSort на этом массиве требует n рекурсий, или 100000. Это много. Рассмотрим лучший алгоритм сортировки или тот, который не использует рекурсию, или подумайте о повторной записи его без рекурсии.

Answer 2

Вы засекретили рекурсивный алгоритм, который ставит сильное давление на стек, а затем дал ему большой набор данных, который при условии, что стек давление пропорционально квадрату размера проблемы, не оставляет никакой тайны относительно того, почему у вас переполнение стека. Перекодируйте свой алгоритм в виде цикла и не оставляйте столько мусора в стеке.