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
