CODEWITHSUNDEEP
javasortingquicksort
Mighty
Mighty

Reputation: 37

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.

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)

Upvotes: 2

Views: 349

Answers (1)

GBlodgett
GBlodgett

Reputation: 12819

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 

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:

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

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

Upvotes: 2

Related Questions