'Issues with Iterative quicksort
I am having issues with 2 pivot strategies, median of 3 random elements (corresponding to the quickSortThreeRandomPivot() method) & random element (corresponding to the quickSortRandomPivot() method). I am pretty sure the error is originating from where I set the range of random numbers (indices).
Currently, this is code I am using to try to accomplish this: quickSortRandomPivot():
pivot = (int) list.get(ThreadLocalRandom.current().nextInt((last - first) + first));
quickSortThreeRandomPivot():
int num1 = (int) list.get(ThreadLocalRandom.current().nextInt(**(last - first) + first)**);
int num2 = (int) list.get(ThreadLocalRandom.current().nextInt(**(last - first) + first)**);
int num3 = (int) list.get(ThreadLocalRandom.current().nextInt(**(last - first) + first)**);
pivot = medianOfThreeNums(num1, num2, num3);
In my implementation, I am trying to sort the list "in place". So, to update the range of indices to generate random number(s) from, I used the equation (last - first) + first. If the current subarray is being sorted is the left side of the list, the range of indices should be 0 to pivotIndex - 1 (first == 0, last == pivotIndex - 1). If the current subarray is being sorted is the right side of the list, the range of indices should be pivotIndex + 1 to the size of the list - 1 (first == pivotIndex + 1, last == list.size() - 1).
However, when I run my code, I get the corresponding error below for array sizes greater than or equal to 100:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100 out of bounds for length 100
at QuickSorter.quickSortRandomPivot(QuickSorter.java:261)
at QuickSorter.timedQuickSort(QuickSorter.java:31)
at DriverClass.main(DriverClass.java:56)
Is there something wrong with my logic? Any advice will help a lot, as my professor seems to be unable to help me resolve the issue :/
Here is my code:
Class that contains quicksorting methods:
import java.lang.*;
import java.time.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.io.*;
public class QuickSorter{
// This method takes in the randomly generated ArrayList and the specified pivot strategy, and sorts the
// ArrayList based on the specified pivot strategy.
// This method returns (roughly) the amount of time it took to sort the ArrayList.
public static <E extends Comparable<E>> Duration timedQuickSort(ArrayList<E> list, PivotStrategy pivotStrategy){
// Throw a NullPointerException if either of the arguments to this method are null.
if(list == null || pivotStrategy == null){
throw new NullPointerException("Error: the arguments to timedQuickSort() cannot be null.");
}
int first = 0; // Holds the index of the 1st element (0).
int last = list.size() - 1; // Holds the index of the last element.
Duration pivotStratDuration; // Used to determine the execution time of the selected pivot strategy.
// Determine the pivot strategy and call the appropriate function to begin sorting.
switch(pivotStrategy){
case FIRST_ELEMENT:
// Begin sorting and return the execution time of the quicksort operations.
pivotStratDuration = quickSortFirstElementPivot(list, first, last);
break;
case RANDOM_ELEMENT:
// Begin sorting and return the execution time of the quicksort operations.
pivotStratDuration = quickSortRandomPivot(list, first, last);
break;
case MEDIAN_OF_THREE_RANDOM_ELEMENTS:
// Begin sorting and return the execution time of the quicksort operations.
pivotStratDuration = quickSortThreeRandomPivot(list, first, last);
break;
case MEDIAN_OF_THREE_ELEMENTS:
// Begin sorting and return the execution time of the quicksort operations.
pivotStratDuration = quickSortThreePivot(list, first, last);
break;
default:
// Have the default case be the 1st element of the array as the pivot.
// Begin sorting and return the execution time of the quicksort operations.
pivotStratDuration = quickSortFirstElementPivot(list, first, last);
break;
}
// Return the execution time of the quicksort method, with the selected pivot strategy.
return pivotStratDuration;
}
/*
// This method sets the selected pivot (based on the PivotStrategy), places the pivot element at is correct position in the unsorted ArrayList,
// and places all smaller elements (smaller than the pivot) to the left of the pivot and all greater elements to the right of the pivot.
private static <E> int partition(ArrayList<E> currentList, int low, int high, int selectedPivot){
// Index of the smaller element indicates the right position of pivot found so far.
int i = (low - 1);
for(int j = low; j <= high - 1; j++){
// If current element is smaller than the pivot.
if((int) currentList.get(j) <= selectedPivot){
// Increment index of the smaller element.
i++;
swap(currentList, i, j);
}
}
swap(currentList, i + 1, currentList.indexOf(selectedPivot));
return (i + 1);
}
*/
private static <E> int partition(ArrayList<E> currentList, int low, int high, int selectedPivot){
// This loop terminates when low >= right.
while(true) {
while((int) currentList.get(low) < selectedPivot) {
low++;
}
while((int) currentList.get(high) > selectedPivot) {
high--;
}
if(low >= high){
return high;
}
swap(currentList, low, high);
}
}
/*
private static <E> int partition(ArrayList<E> currentList, int low, int high, int selectedPivot){
int leftPtr = low;
int rightPtr = high - 1;
while(true){
while((int) currentList.get(++leftPtr) < selectedPivot);
while(rightPtr > 0 && (int) currentList.get(--rightPtr) > selectedPivot);
if(leftPtr >= rightPtr){
break;
}
else{
swap(currentList, leftPtr, rightPtr);
}
}
swap(currentList, leftPtr, high);
return leftPtr;
}
*/
// This enum helps timedQuickSort determine what pivot strategy it should use to sort the ArrayList.
public static enum PivotStrategy{
// Pivot is the 1st element in the ArrayList.
FIRST_ELEMENT,
// Pivot is a randomly chosen element in the ArrayList (from index 0 to size - 1).
RANDOM_ELEMENT,
// Pivot is the median of 3 randomly chosen elements in the ArrayList (from index 0 to size - 1).
MEDIAN_OF_THREE_RANDOM_ELEMENTS,
// Pivot is the median of the 1st, middle, and last elements in the ArrayList.
MEDIAN_OF_THREE_ELEMENTS
};
// This helper method is used to swap 2 elements.
private static <E> void swap(ArrayList<E> currentList, int k, int r){
E temp = currentList.get(k);
currentList.set(k, currentList.get(r));
currentList.set(r, temp);
}
// This method generates a random ArrayList of integers of a specified size.
public static ArrayList<Integer> generateRandomList(int size){
// The size of the ArrayList should not be negative (or 0). If it is, throw an IllegalArgumentException.
if(size <= 0){
throw new IllegalArgumentException("Error: the size of the list cannot be less than or equal to 0.");
}
ArrayList<Integer> unsortedList = new ArrayList<>(); // Create an ArrayList to hold random & unsorted values.
// Generate a list of n random numbers.
for(int i = 0; i < size; i++){
Random randomNum = new Random();
unsortedList.add(i, randomNum.nextInt());
}
// Return the unsorted list of random numbers.
return unsortedList;
}
// This helper method finds the median value of 3 numbers (int).
private static <E extends Comparable<E>> E medianOfThreeNums(E a, E b, E c){
// Check if b is the median value (a.compareTo(b) < 0 is the same as a < b).
if((a.compareTo(b) < 0 && b.compareTo(c) < 0) || (c.compareTo(b) < 0 && b.compareTo(a) < 0)){
return b;
}
// Check if a is the median value.
else if(((b.compareTo(a) < 0 && a.compareTo(c) < 0) || (c.compareTo(a) < 0 && a.compareTo(b) < 0))){
return a;
}
else{ // Otherwise, c is the median value.
return c;
}
}
// This method performs the quick sort operations in an iterative fashion, with the 1st element in the array as the pivot.
// It returns the execution time of the quicksort operations.
private static <E> Duration quickSortFirstElementPivot(ArrayList<E> list, int first, int last){
int pivot; // Holds the pivot.
// Create an auxiliary stack.
int[] stack = new int[last - first + 1];
// Initialize the top of the stack.
int top = -1;
// Push the initial values of low and high onto the stack.
stack[++top] = first;
stack[++top] = last;
// The start and end variables are used to calculate the amount of time (in nano seconds) it takes to sort the list with the given pivot strategy.
long start1 = System.nanoTime();
// Keep popping off the stack while it is not empty.
while(top >= 0){
// Pop low and high.
last = stack[top--];
first = stack[top--];
// Set the pivot to the 1st element in the array.
pivot = (int) list.get(first);
// partitionIndex = partitioning index; array[partitionIndex] is now in its true location.
int partitionIndex = partition(list, first, last, pivot);
// If there are elements on the left side of the pivot, then push the left side of the array to the stack.
if(partitionIndex - 1 > first){
stack[++top] = first;
stack[++top] = partitionIndex - 1;
}
// If there are elements on the right side of the pivot, then push them to the right side of the array to the stack.
if(partitionIndex + 1 < last){
stack[++top] = partitionIndex + 1;
stack[++top] = last;
}
}
long end1 = System.nanoTime();
Duration pivotStratDuration = Duration.ofNanos(end1 - start1);
return pivotStratDuration;
}
// This method performs the quick sort operations in an iterative fashion, with a random element in the array as the pivot.
// It returns the execution time of the quicksort operations.
private static <E> Duration quickSortRandomPivot(ArrayList<E> list, int first, int last){
int pivot; // Holds the pivot.
// Create an auxiliary stack.
int[] stack = new int[last - first + 1];
// Initialize the top of the stack.
int top = -1;
// Push the initial values of low and high onto the stack.
stack[++top] = first;
stack[++top] = last;
// The start and end variables are used to calculate the amount of time (in nano seconds) it takes to sort the list with the given pivot strategy.
long start1 = System.nanoTime();
// Keep popping off the stack while it is not empty.
while(top >= 0){
//if (last - first < 2) { continue; }
// Pop low and high.
last = stack[top--];
first = stack[top--];
// Set the pivot as a random element contained within the array.
// Passing (last - first) + first reduces the range of the indices in the list after each while loop iteration.
// If the current sub array is being sorted is the left side of the original list, range of indices: (first == 0, last == pivotIndex - 1).
// If the current sub array is being sorted is the right side of the original list, range of indices: (first == pivotIndex + 1, last == list.size() - 1).
pivot = (int) list.get(ThreadLocalRandom.current().nextInt((last - first) + first));
// partitionIndex = partitioning index; array[partitionIndex] is now in its true location.
int partitionIndex = partition(list, first, last, pivot);
// If there are elements on the left side of the pivot, then push the left side of the array to the stack.
if(partitionIndex - 1 > first){
stack[++top] = first;
stack[++top] = partitionIndex - 1;
}
// If there are elements on the right side of the pivot, then push them to the right side of the array to the stack.
if(partitionIndex + 1 < last){
stack[++top] = partitionIndex + 1;
stack[++top] = last;
}
}
long end1 = System.nanoTime();
Duration pivotStratDuration = Duration.ofNanos(end1 - start1);
return pivotStratDuration;
}
// This method performs the quick sort operations in an iterative fashion, with the median of 3 random elements as the pivot.
// It returns the execution time of the quicksort operations.
private static <E> Duration quickSortThreeRandomPivot(ArrayList<E> list, int first, int last){
int pivot; // Holds the pivot.
// Create an auxiliary stack.
int[] stack = new int[last - first + 1];
// Initialize the top of the stack.
int top = -1;
// Push the initial values of low and high onto the stack.
stack[++top] = first;
stack[++top] = last;
// The start and end variables are used to calculate the amount of time (in nano seconds) it takes to sort the list with the given pivot strategy.
long start1 = System.nanoTime();
// Keep popping off the stack while it is not empty.
while(top >= 0){
//if (last - first < 2) { continue; }
// Pop low and high.
last = stack[top--];
first = stack[top--];
// Set the pivot as 3 random elements contained within the array.
// Passing (last - first) + first reduces the range of the indices in the list after each while loop iteration.
// If the current sub array is being sorted is the left side of the original list, range of indices: (first == 0, last == pivotIndex - 1).
// If the current sub array is being sorted is the right side of the original list, range of indices: (first == pivotIndex + 1, last == list.size() - 1).
int num1 = (int) list.get(ThreadLocalRandom.current().nextInt((last - first) + first));
int num2 = (int) list.get(ThreadLocalRandom.current().nextInt((last - first) + first));
int num3 = (int) list.get(ThreadLocalRandom.current().nextInt((last - first) + first));
pivot = medianOfThreeNums(num1, num2, num3);
// partitionIndex = partitioning index; array[partitionIndex] is now in its true location.
int partitionIndex = partition(list, first, last, pivot);
// If there are elements on the left side of the pivot, then push the left side of the array to the stack.
if(partitionIndex - 1 > first){
stack[++top] = first;
stack[++top] = partitionIndex - 1;
}
// If there are elements on the right side of the pivot, then push them to the right side of the array to the stack.
if(partitionIndex + 1 < last){
stack[++top] = partitionIndex + 1;
stack[++top] = last;
}
}
long end1 = System.nanoTime();
Duration pivotStratDuration = Duration.ofNanos(end1 - start1);
return pivotStratDuration;
}
// This method performs the quick sort operations in an iterative fashion, with the median of the 1st, middle, and last elements in the array as the pivot.
// It returns the execution time of the quicksort operations.
private static <E> Duration quickSortThreePivot(ArrayList<E> list, int first, int last){
int pivot; // Holds the pivot.
// Create an auxiliary stack.
int[] stack = new int[last - first + 1];
// Initialize the top of the stack.
int top = -1;
// Push the initial values of low and high onto the stack.
stack[++top] = first;
stack[++top] = last;
// The start and end variables are used to calculate the amount of time (in nano seconds) it takes to sort the list with the given pivot strategy.
long start1 = System.nanoTime();
// Keep popping off the stack while it is not empty.
while(top >= 0){
// Pop low and high.
last = stack[top--];
first = stack[top--];
// Calculate (roughly) the middle index of ArrayList.
int mid = (first + last) / 2;
// Set the pivot as the median of the 1st, middle (roughly), and last elements within the array.
int number1 = (int) list.get(first);
int number2 = (int) list.get(mid);
int number3 = (int) list.get(last);
pivot = medianOfThreeNums(number1, number2, number3);
// partitionIndex = partitioning index; array[partitionIndex] is now in its true location.
int partitionIndex = partition(list, first, last, pivot);
// If there are elements on the left side of the pivot, then push the left side of the array to the stack.
if(partitionIndex - 1 > first){
stack[++top] = first;
stack[++top] = partitionIndex - 1;
}
// If there are elements on the right side of the pivot, then push them to the right side of the array to the stack.
if(partitionIndex + 1 < last){
stack[++top] = partitionIndex + 1;
stack[++top] = last;
}
}
long end1 = System.nanoTime();
Duration pivotStratDuration = Duration.ofNanos(end1 - start1);
return pivotStratDuration;
}
// This method prints out the list to a specified output file.
public static <E> void printArray(ArrayList<E> list, PrintWriter outputFile){
int newlineCounter = 0; // Used to display a newline after a certain number of elements.
for(int i = 0; i < list.size(); i++){
outputFile.print(list.get(i) + " ");
// Display a newline after 20 elements save been written to the output file to increase readability.
if(newlineCounter == 20){
outputFile.println();
newlineCounter = 0; // Reset counter.
}
else{
newlineCounter++;
}
}
}
}
Driver Class (where main method is located):
import java.io.*;
import java.util.*;
import java.time.*;
/*
How to run program from cmd (windows):
1st command: cd FilePath
2nd command: javac DriverClass.java
3rd command: java DriverClass arraySize reportsFileName unsortedArrayFileName sortedArrayFileName
Note: For the 1st command, the 2 files (DriverClass.java and QuickSorter.java) must be in the same folder.
*/
// args[0] = array size, args[1] = filename for reports file, args[2] = filename to store unsorted array.
// args[3] = filename to store sorted array.
public class DriverClass {
public static void main(String [] args){
PrintWriter reportsFile; // Object for writing the execution time of quicksort for each pivot strategy to an output file.
PrintWriter unsortedListFile; // Object for writing the contents of the unsorted array to an output file.
PrintWriter sortedListFile; // Object for writing the contents of the sorted array to an output file.
// Convert args[0] (string; represents the array size) to an int.
int arraySize = Integer.valueOf(args[0]);
try{
reportsFile = new PrintWriter(new File(args[1])); // Creates an instance of PrintWriter and creates an output file for writing the execution time to.
unsortedListFile = new PrintWriter(new File(args[2])); // Creates an instance of PrintWriter and creates an output file for writing the unsorted list to.
sortedListFile = new PrintWriter(new File(args[3])); // Creates an instance of PrintWriter and creates an output file for writing the sorted list to.
try{
// Generate an array of random numbers with the specified size.
ArrayList<Integer> list = QuickSorter.generateRandomList(arraySize);
// Write the contents of the unsorted list to the unsortedListFile.
QuickSorter.printArray(list, unsortedListFile);
// Write the array size to the reports file.
reportsFile.println("Array Size = " + arraySize + "\n");
// Create 4 pointers that reference the same ArrayList (list).
// This allows each pivot strategy to sort the same set of numbers.
ArrayList<Integer> tempList1 = new ArrayList<>(list);
ArrayList<Integer> tempList2 = new ArrayList<>(list);
ArrayList<Integer> tempList3 = new ArrayList<>(list);
ArrayList<Integer> tempList4 = new ArrayList<>(list);
Duration pivotStrategyDuration; // Holds the execution time of a pivot strategy.
// Begin sorting the array, using the 1st element pivot strategy.
pivotStrategyDuration = QuickSorter.timedQuickSort(tempList1, QuickSorter.PivotStrategy.FIRST_ELEMENT);
// Write the execution time to the reports output file.
reportsFile.println("FIRST_ELEMENT: " + pivotStrategyDuration + "\n");
// Begin sorting the array, using the a random element pivot strategy.
pivotStrategyDuration = QuickSorter.timedQuickSort(tempList2, QuickSorter.PivotStrategy.RANDOM_ELEMENT);
// Write the execution time to the reports output file.
reportsFile.println("RANDOM_ELEMENT: " + pivotStrategyDuration + "\n");
// Begin sorting the array, using the median of 3 random elements pivot strategy.
pivotStrategyDuration = QuickSorter.timedQuickSort(tempList3, QuickSorter.PivotStrategy.MEDIAN_OF_THREE_RANDOM_ELEMENTS);
// Write the execution time to the reports output file.
reportsFile.println("MEDIAN_OF_THREE_RANDOM _ELEMENTS: " + pivotStrategyDuration + "\n");
// Begin sorting the array, using the median of the 1st, middle, and last element pivot strategy.
pivotStrategyDuration = QuickSorter.timedQuickSort(tempList4, QuickSorter.PivotStrategy.MEDIAN_OF_THREE_ELEMENTS);
// Write the execution time to the reports output file.
reportsFile.println("MEDIAN_OF_THREE_ELEMENTS: " + pivotStrategyDuration + "\n");
// Write the one of the sorted lists to the sortedListFile.
QuickSorter.printArray(tempList1, sortedListFile);
}
catch(IllegalArgumentException x){ // Catches the exception where the arraySize <= 0.
reportsFile.println(x.getMessage()); // Write the error message to the report's file.
System.exit(1); // Terminate the program (1 = failure).
}
catch(NullPointerException x){ // Catches the exception where one of the arguments passed to timedQuickSort is null.
reportsFile.println(x.getMessage()); // Write the error message to the report's file.
System.exit(1); // Terminate the program (1 = failure).
}
// Close all the output files.
reportsFile.close();
unsortedListFile.close();
sortedListFile.close();
}
catch(FileNotFoundException x){ // Catches the exception where the one of the output files are unable to be created.
System.out.println("Error: unable to create an output file.");
System.exit(1); // Terminate the program (1 = failure).
}
System.exit(0); // Terminate the program (0 = success).
}
}
Instructions on how to run program:
If you are using IDE that is Eclipse, IntelliJ, or NetBeans, set the program arguments as "arraySize" "reports.txt" "unsortedArray.txt" "sortedArray.txt"
If you not using one of the 3 IDEs above, you must use cmd (windows) with the following commands: 1st command: cd FilePath 2nd command: javac DriverClass.java 3rd command: java DriverClass arraySize reportsFileName unsortedArrayFileName sortedArrayFileName
Note: For the 1st command, the 2 files (DriverClass.java and QuickSorter.java) must be in the same folder.
The report.txt file just holds the size of the array and the execution time for the 4 different pivot strategies.
Thank you for your help and expertise!
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|