Randomized QuickSort IndexOutOfBounds exception

Question

this is the QuickSort Randomized that I've come up with, but it constantly throws out IndexOutOfBounds exception. Could I have some help with it? Thanks!

import java.util.Random;

public class QuickSort {

    void quickSort(int[] A, int start, int end) { // Initially: start = 0, end = n-1
        while (start < end) {
            int iOfPartition = randomisedPartition(A, start, end);
            if (iOfPartition - start < end - iOfPartition) {
                quickSort(A, start, iOfPartition - 1);
                start = iOfPartition + 1;
            } else {
                quickSort(A, iOfPartition + 1, end);
                end = iOfPartition - 1;
            }
        }
    }

    int randomisedPartition(int[] A, int start, int end) {
        Random rng = new Random();
        int randomNum = rng.nextInt(end + 1 - start) + start;
        swap(A, A[randomNum], A[start]);
        return hoarePartition(A, start, end);
    }

    int hoarePartition(int[] A, int start, int end) {
        int pivot = A[start];
        int i = start;
        int j = end;
        while (i < j) {
            while (A[i] <= pivot && i < end) i++;
            while (A[j] > pivot && j > start) j--;
            if (i < j) swap(A, A[i], A[j]); 
        }
        swap(A, A[start], A[j]);
        return j; 
    }

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

I keep getting an arrayindexoutofbounds error.

Answer 1

I echo the sentiment of the comment above, you should learn to use the debugger or print statements to try to piece together what is happening.

Still, I couldn't resist investigating.

Check out what you are doing here in the call to swap. You are taking the value which is in the randomNum position with A[randomNum]

    swap(A, A[randomNum], A[start]); // incorrectly indexing here

But then inside swap, you are repeating the process, and taking the value at the A[A[randomNum]] which does not necessarily exist.

int temp = A[i]; // indexing here again

So your problem is that you are incorrectly indexing twice. You should use [] only in the swap function, not in the randomisedPartition function. randomisedPartition should send swap indexes, not indexed values.

How did I figure this out ? I tried a call with very simple data

int data[] = {5,3,4};
new Example().quickSort(data, 0, 2);

and got an index out of bounds 5 error. That's how you debug.