Quicksort implementation program array out of bounds error and not sorting generated numbers

I am new to programming and cannot seem to figure out my errors when trying to write a Quicksort program. I have most of the implementation done with the exception of a few errors that I cannot seem to figure out. Here is my current code:

public class Quicksort {
public static void main(String args) {

Integer numbers = new Integer[20];
for (int i = 0; i < numbers.length; i++) {
numbers[i] = (int) (Math.random() * 100);
}


printArray(numbers);


quicksort(numbers);


printArray(numbers);
}


public static <T> void printArray(T array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + (i < array.length - 1 ? ", " : "n"));
}
}


public static <T> void printArrayPartition(T array, int low, int high, int pivot) {
for (int i = 0; i < array.length; i++) {
String element = "" + array[i];
if (i == pivot)
element = "*" + element + "*";
if (i == low)
element = "[" + element;
if (i == high)
element += "]";
System.out.print(element + (i < array.length - 1 ? ", " : "n"));
}
}

public static <T extends Comparable<T>> void quicksort(T array) {
quicksort(array, 0, array.length - 1);
}

private static <T extends Comparable<T>> void quicksort(T array, int low, int high) {

if (low < high) {
int pivotIndex = partition(array, low, high);
int pivot = pivotIndex;

printArrayPartition(array, low, high, pivot);

quicksort(array, low - 1, pivotIndex - 1);
quicksort(array, pivotIndex + 1, high + 1);
}
}

private static <T extends Comparable<T>> int partition(T array, int low, int high) {

T pivotValue = array[high];

int left = low;


for (int i = 0; i < array.length; i++) {

if (array[i].compareTo(pivotValue) > 0) {

left++;
}
}

swap(array, high, left);

return left;
}

private static <T> void swap(T array, int a, int b) {
T temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}


When running this program I am getting ArrayIndexOutOfBounds error and I'm not sure why. I have traced few my code a few times and still cannot seem to figure it out.

ArrayIndexOutOfBounds

Stack trace:

54, 91, 26, 43, 98, 65, 88, 78, 88, 60, 58, 75, 74, 46, 79, 81, 64, 49, 67, 31
[54, 91, 26, 43, 98, 65, 88, 78, 88, 60, 58, 75, 74, 46, 79, 81, 64, 49, *31*, 67]
54, 91, 26, 43, 98, 65, 88, 78, 88, 60, 58, 75, 74, 46, *49*, 81, 64, 79], 31, 67
54, 91, 26, 43, 98, 65, 88, 78, 88, 60, 58, 75, 74, 49], *46*, 81, 64, 79, 31, 67
54, 91, 26, 43, 98, 65, 88, 78, 88, 60, 58, 75, *49*, 74], 46, 81, 64, 79, 31, 67
54, 91, 26, *75*, 98, 65, 88, 78, 88, 60, 58, 43], 49, 74, 46, 81, 64, 79, 31, 67
54, 91, 46], 75, 98, 65, 88, 78, 88, 60, 58, 43, 49, 74, *26*, 81, 64, 79, 31, 67
54, 91, *74*, 75, 98, 65, 88, 78, 88, 60, 58, 43, 49, 46], 26, 81, 64, 79, 31, 67
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -6
at Quicksort.swap(Quicksort.java:79)
at Quicksort.partition(Quicksort.java:72)
at Quicksort.quicksort(Quicksort.java:47)
at Quicksort.quicksort(Quicksort.java:52)
at Quicksort.quicksort(Quicksort.java:52)
at Quicksort.quicksort(Quicksort.java:52)
at Quicksort.quicksort(Quicksort.java:52)
at Quicksort.quicksort(Quicksort.java:52)
at Quicksort.quicksort(Quicksort.java:52)
at Quicksort.quicksort(Quicksort.java:52)
at Quicksort.quicksort(Quicksort.java:41)
at Quicksort.main(Quicksort.java:13)


Please post the full stackTrace and what line is causing the error
– GBlodgett
2 days ago

Just updated my post with it.
– Mighty
2 days ago

Your swap(array, high, left) method implementation ??
– Madushan Perera
2 days ago

swap(array, high, left)

Yes, that is my intention
– Mighty
2 days ago

idownvotedbecau.se/nodebugging
– Andreas
2 days ago

1 Answer
1

In your recursive calls:

quicksort(array, low - 1, pivotIndex - 1);
quicksort(array, pivotIndex + 1, high + 1);


You subtract one from low and pivotIndex and then later pass those values to

low

pivotIndex

swap(array, high, left); //via int left = low;


Which in turn calls the index of high and low. When you start the method low is set to zero. And then you subtract one to get a negative number. If the condition: if (array[i].compareTo(pivotValue) > 0) is never met then left will never be increased and you will be passing a negative number to swap(…). And in the swap() method:

high

low

low

if (array[i].compareTo(pivotValue) > 0)

left

swap(…)

swap()

T temp = array[a]; //a is left here
array[a] = array[b];
array[b] = temp;


You directly try to call the index of left which might be a negative number, thus the indexoutofboundsexception with a negative index

left

indexoutofboundsexception

And in the same fashion the quicksort(array, pivotIndex + 1, high + 1); can add one to high and thus cause it to go out of bounds

quicksort(array, pivotIndex + 1, high + 1);

high

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.