Java - Implementing QuickSort

Question

I'm learning datastructures and algorithms. So I have tried implementing the quick sort alogorithm.

public static void main(String[] args) {
    // TODO Auto-generated method stub

    int[] arr = new int[] { 10, 16, 8, 12, 15, 6, 3, 9, 5 };

    quickSort(0, arr.length - 1, arr);
}

public static void quickSort(int start, int end, int[] arr) {

    if (start < end) {

        int partitionIndex = partition(start, end, arr);
        quickSort(start, partitionIndex - 1, arr);
        quickSort(partitionIndex+1, end, arr); // When passing partitionIndex+1 in the swap method it throws index out of bound exception

        System.out.println(Arrays.toString(arr));
    }   

}

public static int partition(int start, int end, int[] arr) {

    int pivot = arr[end];
    int pIndex = start;

    for (int i = 0; i < end - 1; i++) {

        if (arr[i] <= pivot) {
            swap(i, pIndex, arr);
            pIndex++;
        }
    }

    swap(pIndex, end, arr);
    return pIndex;

}

private static void swap(int i, int index, int[] arr) {

    int temp = arr[i];
    arr[i] = arr[index]; // index out of bound exception is thrown
    arr[index] = temp;

}

When doing the recursive call quickSort(partitionIndex+1, end, arr); and in the swap method it is throwing index out of bound exception. Because there is no such index to retrieve/store the value. Can any one please help me to resolve this issue?

Samuel Philipp · Accepted Answer · 2019-02-21T18:52:18.900

1

I assume you tried to implement the Lomuto partition scheme from Wikipedia. If that's the case you have 2 errors in your code, both in the for loop of the partition method:

start index:

You algorithm starts every time at 0. That is causing the IndexOutOfBoundsException, because it swaps pIndex which is array.length at the end. If you fix this, the exception will be gone, but your sorted result will be [3, 5, 8, 10, 12, 15, 6, 16, 9], which is obviously not perfectly sorted.

end condition:

The error here is, that the last iteration is missing every time, because your end condition is i < end - 1 change that to i < end or i <= end - 1 and you should get a perfect result:

[3, 5, 6, 8, 9, 10, 12, 15, 16]

For completion here is the fixed partition method and your quickSort method:

public static void quickSort(int start, int end, int[] arr) {
    if (start < end) {
        int partitionIndex = partition(start, end, arr);
        quickSort(start, partitionIndex - 1, arr);
        quickSort(partitionIndex + 1, end, arr);
    }
}

public static int partition(int start, int end, int[] arr) {
    int pivot = arr[end];
    int pIndex = start;
    for (int i = start; i < end; i++) {
        if (arr[i] < pivot) {
            swap(pIndex, i, arr);
            pIndex++;
        }
    }
    swap(pIndex, end, arr);
    return pIndex;
}

edited Feb 21 '19 at 18:52

answered Feb 21 '19 at 18:37

Samuel Philipp

10,631
12
36
56

If i change this to i < end or i <= end - 1, i'm getting stack overflow error – Aishu Feb 21 '19 at 18:44
Have you changed the `quickSort` method? – Samuel Philipp Feb 21 '19 at 18:47
Not sure, where exactly to change. Could you please tell me? – Aishu Feb 21 '19 at 18:48
`partitionIndex + 1` is required for the second recursion call. – Samuel Philipp Feb 21 '19 at 18:48
I added the `quickSort` method to my answer, so ist complete now, except the `swap` method. – Samuel Philipp Feb 21 '19 at 18:53
This works. Thanks a lot :) – Aishu Feb 21 '19 at 19:05

Java - Implementing QuickSort

1 Answers1