0

I've encountered some issue with one of my do-while loops while trying to implement quickSort, scpecifically in partitioning method. This particular loop is causing problems since the index is getting out of bounds and honestly I don't know why:

do {
    j--;
} while (array[j] > pivot);

and full code:

public static void main(String[] args) {

        int tab[] = {-5, 12, 6, -2, 7, 9, 1};

        quickSort(tab, 0, tab.length-1);

        for (int x: tab){
            System.out.print(x+" ");
        }
    }

    public static int partition(int array[], int left, int right){

        int pivot = array[left];
        int i = left;
        int j = right;

        while (i < j) {
            do {
                i++;
            } while (array[i] <= pivot);

            do {
                j--;
            } while (array[j] > pivot);

            if (i < j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
            int temp = pivot;
            pivot = array[j];
            array[j] = pivot;

        return j;
    }


    public static void quickSort(int array[], int left, int right){
        if (left < right) {
            int pivot = partition(array, left, right);
            quickSort(array, left, pivot);
            quickSort(array, pivot + 1, right);
        }
    }

Kind regards,

crystalsky
  • 35
  • 6
  • 2
    What do you mean you don't know why? You decrement a counter and then use it without checking that it's in range. Either test the value after decrementing or consider a while loop (block executes 0 or more times) vs. a do while loop (block executes 1 or more times). – MarsAtomic Aug 28 '21 at 22:53
  • @MarsAtomic ok, it took me a while, but for some reason I thought that I was comparing 2 with -5 and not -2 with -5. Anyway, I know where is the problem right now since like you wrote, there is no control for situations like in my array :). – crystalsky Aug 28 '21 at 23:02
  • 1
    Great job. When you run into situations like this, run your code through the debugger and you can usually spot what's going on right away. – MarsAtomic Aug 28 '21 at 23:11

0 Answers0