Java Quicksort why / where do the values change?

Question

I'm learning Java in school right now and our latest topic are sort algorithms in Java. The one that I'm trying to understand is quicksort.

To understand how that algorithm sorts numbers in an array I decided to go through my code step for step in the Eclipse debugger window.

Now there was one step that I can not comprehend even after going through it what felt like hundreds of times.

My initial array is [10, 5, 3, 22, 11, 2]

When I go through the code the program starts by swapping 10 and 2, then 5 and 3 and then 2 and 2. At that point the value for i is 1 and the value for j is -1.

Now the way I see it is that there are three conditions

1. while(i<=j) Which returns false, because i = 1 and j = -1

2. if(left < j) Which returns false, because left = 0 and j = -1

3. if(i < right) Which also returns false, because i = 1 and right = 1

But to my surprise when the program gets to the last bracket right before public static void display the program skips back to line 40 if(i < right) but suddenly the values for right, i, j and pivot have changed from to 5, 2, -1, and 3 respectively.

I would be very grateful if someone could explain why the values get changed.

I have also added two pictures which show what I see on my Eclipse window step I don't understand

public class QSort {

    public static void quickSort(int[] arr, int left, int right){
        int i = left;
        int j = right;
        int temp;
        int pivot = arr[(left+right)/2];
        System.out.println("\n\nleft = " + left + "\tright = " + right);
        System.out.println("Pivot is: " + pivot + "(" +  (left+right)/2 + ")");
        while(i <= j){
            while(arr[i] < pivot){
                System.out.println("i is: " + arr[i] + "(" + i + ")");
                i++;
                System.out.println("i is: " + arr[i] + "(" + i + ")");
            }
            while(arr[j] > pivot){
                System.out.println("j is: "+ arr[j] + "(" + j + ")");
                j--;
                System.out.println("j is: "+ arr[j] + "(" + j + ")");
            }
            if(i <= j){
                System.out.println("i is: " + arr[i] + "(" + i + ")");
                System.out.println("j is: "+ arr[j] + "(" + j + ")");
                System.out.println("Swapped " + arr[i] + "(" + i + ")"+ " with " + arr[j] + "(" + j + ")");
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
                System.out.println("i is: (" + i + ")");
                System.out.println("j is: (" + j + ")");
                System.out.println("Pivot is: " + pivot + "(" +  (left+right)/2 + ")");
            }
        }
        if(left < j){
            System.out.println("j is: (" + j + ")");
            quickSort(arr, left, j);
        }
        if(i < right){
            System.out.println("i is: (" + i + ")");
            quickSort(arr, i, right);
        }
    }

    public static void display(int[] arr){
        if(arr.length > 0){
            System.out.print(arr[0]);
        }
        for(int i = 1; i < arr.length; i++){
            System.out.print(", " + arr[i]);
        }
    }

    public static void main(String[] args) {
        int[] data = new int[]{10,5,3,22,11,2};
        System.out.println("Before: ");
        display(data);
        quickSort(data, 0, data.length-1);
        System.out.println("\nAfter: ");
        display(data);
    }
}

Thanks a lot!

Answer 1

I think your problem is that you don't fully understand recursion. At least that's what it sounds like from your desription of the question.

Anyway, I've tried to simply follow your program by keeping a trace of all variables. Hope this helps:

arr                 left       right      i         j      pivot
-----------------   -------    --------   -------   -----  ----------
[10,5,3,22,11,2]    0          5         
                                          0         5      arr[2] = 3
[2,5,3,22,11,10]                          1         4
                                                    3
                                                    2
[2,3,5,22,11,10]                          2         1

The while loop has finished because i<=j is now false (2 > 1).

The first condition left < j (0 < 1) is true, so you call quicksort again recursively: quicksort(arr, 0, 1) - which means you now sort the array [2,3] which is already sorted, so nothing will happen:

arr                 left       right      i         j      pivot
-----------------   -------    --------   -------   -----  ----------
[2,3,5,22,11,10]    0          1
                                          0         1      arr[0] = 2
                                                    0
[2,3,5,22,11,10]                          1         -1

The while loop condition is now false. The first condition left < j is false as well (because 0 > -1) and the second condition i < right is also false (because 1 == 1) So this call is finished and you return to where you were. Were was that? The first condition of the table above. The state of variables and parameters is now:

arr                 left       right      i         j      pivot
-----------------   -------    --------   -------   -----  ----------
[10,5,3,22,11,2]    0          5         2          1      3

The second condition is checked (as it is the next line executed). Its value is also true since the condition is i < right (2 < 5). So you now do quicksort again recursively: quicksort(arr, 2, 5) - which means you now sort the array [3,22,11,10]:

arr                 left       right      i         j      pivot
-----------------   -------    --------   -------   -----  ----------
[2,3,5,22,11,10]         2          5         
                                          2         5      arr[3] = 22
                                          3
[2,3,5,10,11,22]                          4         4
                                          5

i > j now so we exit the while loop.

The first condition left < j (2 < 4) is true, so we call quicksort(arr, 2, 4) in order to sort [5,10,11] which is already sorted. I'll skip this part as it does not change the array at all.

When the recursive call is done, we return to where we were and now the second condition will be checked. i < right (5 < 5) is false And so we're done.

The original quicksort call has finished and the array is sorted.

Answer 2

The first picture you have shows the debugger is inside two recursive invocations of quicksort: quicksort is called from main, and then on line 38 calls quicksort again (this is the principle of quicksort, it's a recursive strategy). So you see you're on line 40 of the inner call, then when you step from there, you go back to the previous invocation of quicksort (the debugger shows you a stack of two lines instead of three in the top left window), and you're back to the previous values of pivot, etc. The array is passed as is to all recursive invocations so it's shared, but the integer variables aren't.

I think here it's the recursion that makes it hard to understand, check your call stack.