1

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.

talex
  • 17,973
  • 3
  • 29
  • 66
Roo
  • 13
  • 3
  • Can you share the stacktrace of exception and also the comments on what each function does would be helpful – Richard Stokes Aug 26 '21 at 14:52
  • 1
    I prefer to give you a rod rather than a fish. I understand this is some kind of learning process, as normally you would never ever write your own code for something that has been implemented for ages (and works fine). As qsort is recursive by nature all you need to do is to debug or write somewhere (by system.out.println or whatever) the subsequent calls at the beginning of your quickSort method. You will see in no time values that are less than zero or bigger than the length of the array as this is what this exception is all about. Good luck! – Bart Aug 26 '21 at 14:54
  • In `hoarePartition()`, `i` should start at `start+1`, not `start` - `start` is the pivot slot. Also, the `while`s can terminate if `i` and `j` cross (meet). – 500 - Internal Server Error Aug 26 '21 at 15:51
  • @500-InternalServerError thanks all for this, but here i think i=start+1 doesn't matter?because my A[i] <= pivot already, so start+1 would just mean A[i] – Roo Aug 26 '21 at 17:01
  • @Roo: You are correct. The first comparison, between `pivot` and `A[start]`, is redundant, but it's no big deal. – 500 - Internal Server Error Aug 26 '21 at 19:03

1 Answers1

0

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.

Gonen I
  • 5,576
  • 1
  • 29
  • 60
  • 1
    Yes, thank you for this. This error was because initially i defined the function swap as swap(int i, int j) without realising i needed swap(int[]A, int i, int j) to edit the array itself. Then i conveniently ignored the swap function after correcting it as i foolishly thought it was minor. *facepalm* I'm new to using IntelliJ and programming in general, but will learn how to debug properly next time, if you have any debugging tips, I'd appreciate them, thank you for your help! :) – Roo Aug 26 '21 at 17:08
  • Any debugging tips? Don't get me started, I've got a million of them. :) Basically it's all about starting at the failure point and back tracing from there. Minimize the data , for example start with a tiny array like I did. Then look at the exception. If it says IndexOutofBounds[5] at Example.swap(Example.java:39) you go to that line and print all the variables to see which one is 5. Then you think, ok how did I get here? Who sent the 5 there? You go to the calling function and and print statements there ( or Breakpoints if using a debugger ). Happy learning :) – Gonen I Aug 26 '21 at 20:50