Quicksort doesn't run Java

Question

Im trying to make a Quicksort but it always showing up the Error ArrayIndexOutOfBoundsException.

public class Quicksort
{
    void sort(int[] arr)
    {
        _quicksort(arr, 0, arr.length - 1);
    }
    private void _quicksort(int[] arr, int left, int right)
    {
        int pivot = (left + right)/2;
        int l = left;
        int r = right;
        while (l <= r)
        {
            while (arr[l] < pivot)
            {
                l++;
            }
            while (arr[r] > pivot)
            {
                r--;
            }
            if(l <= r)
            {
                int temp = l;
                l = r;
                r = temp;
                l++;
                r++;
            }
        }
        if(left < r)
        {
            _quicksort(arr, left, r);
        }
        if(l < right)
        {
            _quicksort(arr, l, right);
        }
    }
}

Does someone know why it doesnt run? It always gives a Error.

The Error message is

java.lang.ArrayIndexOutOfBoundsException: -1
    at Quicksort._quicksort(Quicksort.java:18)
    at Quicksort._quicksort(Quicksort.java:33)
    at Quicksort.sort(Quicksort.java:5)

Error Message

Answer 1

It seems like there are a couple of issues with your code. I've listed them below:

1. The variable pivot stores the index of the pivot element and not the actual value. So, you can't use pivot for comaparison as you have done in the 2 nested while loops. You need arr[pivot] instead of pivot there.

2. Imagine arr looks like {1, 1, 1, 3, 2, 2, 2}. Here, pivot will be equal to 3 i.e. arr[pivot] will be equal to 3. Now, after both the nested while loops terminate, l will be equal to 3 and r will remain equal to 6. You then swap arr[l] and arr[r] and increment both l and r. Since l is still less than equal to r, the outer while loop runs for a second time and you'll get an ArrayIndexOutOfBoundsExecption when the control reaches the second nested while loop. This happens because you're trying to access arr[7] (Out of Bounds).

Here's my code:

class Quicksort
{
    void sort(int[] arr)
    {
        myQuicksort(arr, 0, arr.length - 1);
    }

    private void myQuicksort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }

        int pivotIndex = (l + r) / 2;
        swap (arr, r, pivotIndex);

        int pivotValue = arr[r];
        int swapIndex = 0;
        int currentIndex = 0;

        while (currentIndex != r) {
            if (arr[currentIndex] < pivotValue) {
                swap(arr, currentIndex, swapIndex);
                swapIndex++;
            }

            currentIndex++;
        }

        swap(arr, r, swapIndex);

        myQuicksort(arr, l, swapIndex - 1);
        myQuicksort(arr, swapIndex + 1, r);
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

public class Main{
    public static void main(String[] args) {
        Quicksort quicksort = new Quicksort();

        int[] arr = {3, 7, 1, 0, 4};
        quicksort.sort(arr);

        for (int i : arr) {
            System.out.println(i);
        }
    }
}

You should read up on Quicksort. But here are the main points:

1. Choose a random pivot element and swap it with the last element. This makes the implementation much simpler.

2. Loop over the input array and keep a track of a swapIndex such that everything before the swapIndex is less than the pivotValue and everything from the swapIndex till the currentIndex is greater than (or equal) the pivotValue.

3. After the loop runs out, swap the element at swapIndex with the pivot. This inserts the pivot in its correct position.

4. The pivot divides the array into 2 subarrays. Call myQuicksort on these 2 subarrays.