Jason Snook - 1 year ago 62

Java Question

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

Answer Source

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.