[FIXED] Java - StackOverflowError when executing QuickSort with large size (100,000) array

Issue

Working on an assignment measuring QuickSort efficiency in System.nanoTime. I have the code working for other array sizes (e.g. 100; 1,000; 10,000), however, when I attempt the method using an array of size 100,000, I am receiving a StackOverflowError. It is also good to note that I have this working for and array of size 100,000 for InsertionSort and BubbleSort.

The goal is to run through QuickSort 105 times, measuring the 100 times following the first 5, with the array, measuring the runtime in nanoTime.

First, I am creating a random int array of the predetermined size. Next, I am cloning that int array and passing the clone to the desired sort method (QuickSort in this instance). Finally, I have created a method to run through the required number of times using QuickSort. The method is as follows:

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 is set to 105 and DIVISOR is set to 100. The instructor-supplied QuickSort code is as follows:

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;
}

What am I doing wrong? One final thought, I am using NetBeans on a newer MacBook Pro. Just wanted to be sure I shared everything. Any help would be greatly appreciated!

UPDATE: This is the code I used to generate array:

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

Solution

Short version: Your list is sorted and QS requires a lot of recursion for sorted lists.

QuickSort is a recursive algorithm with a worst case time complexity of O(n), which is attained, for your pivot choice (first item), when the list is sorted.

Which it is, after the first iteration, because QuickSort sorts in place, i.e. it modifies the input array.

After your first iteration, the QuickSort on that array requires n recursions, or 100000. That's a lot. Consider a better sorting algorithm, or one that does not use recursion, or consider re-writing it without recursion.

Answered By - njzk2
Answer Checked By - Mildred Charles (JavaFixing Admin)