Java Quicksort, why / where do values ​​change?

Question

I am learning Java at school right now, and our last topic is Java sorting algorithms. The one I'm trying to understand is quickly sorted.

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

Now there was one step that I cannot understand even after going through it, which was like hundreds of times.

My starting array [10, 5, 3, 22, 11, 2]

When I look at the code, the program starts by replacing 10 and 2 , then 5 and 3 , and then 2 and 2 . At this point, the value of i is 1 , and the value for j is -1 .

Now, as I see, there are three conditions

• while(i<=j) Returns false because i = 1 and j = -1

• if(left < j) Which returns false because left = 0 and j = -1

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

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

I would be very grateful if anyone could explain why the meanings are changing.

I also added two pictures that show what I see in the Eclipse window a step that I do not 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 do not fully understand recursion. At least that's what your description of the question seems to be.

In any case, I tried to just follow your program, keeping traces of all variables. Hope this helps:

 arr left right ij 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 is complete because i<=j now false ( 2 > 1 ).

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

 arr left right ij 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 (because 0 > -1 ), and the second condition i < right also false (because 1 == 1 ). Thus, this call is completed, and you will return to where you were. Was that so? The first condition of the table above. Now the state of the variables and parameters:

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

The second condition is checked (since the next line is true). Its value is also true, since the condition i < right ( 2 < 5 ). So, now you are quicksort again recursively: quicksort(arr, 2, 5) - this means that now you are sorting the array [3,22,11,10] :

 arr left right ij 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 , so we exit the while loop.

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

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

The original quicksort call quicksort complete and the array is sorted.

Answer 2

The first image you have shows that the debugger is inside two recursive quicksort calls: quicksort is called from main, and then quicksort is called again on line 38 (this is the principle of quick sorting, this is a recursive strategy). So, you see that you are in line 40 of the internal call, and then when you go from there, you return to the previous quicksort call (the debugger shows you a stack of two lines instead of three in the upper left window), and you are returned to the previous values turning etc The array is passed as for all recursive calls, so it is divided, but integer variables are not.

I think there is a recursion here that makes it hard to understand, check the call stack.

Answer 3

Your efforts to learn sorting algorithms using print operators and a debugger are commendable! But your current implementation of Quicksort is pretty hard to understand, at least initially, because it has iteration and recursion (i.e. you use loops, and at the same time you have a quicksort procedure that calls itself).

Let's look at a completely different approach (a purely recursive approach) to see how Quicksort works and why it works. Converting this recursive procedure to an iterative one (as you wrote it), fortunately, is a technical matter (in this case)! I suggest that we do this here, because in this way we could better control complexity. Again, the reason I do this is to better understand what is happening .

When Sir Tony Hoar proposed an algorithm and proved its correctness, it was something like this:

  public static void qsort(int[] ints, int fi, int li) { /* the recursive procedure */ if (fi < li) { int p = partition(ints, fi, li); // key routine -- see below qsort(ints, fi, p - 1); qsort(ints, p + 1, li); } } 

What is it! Not beautiful? Well it is. All you do is:

• Divide this array. In my opinion, splitting is an elegant procedure to solve a complex problem. The problem is simple: set an array of numbers, rearrange the array so that it contains a number, all numbers to the left of which are less than or equal to it, and all numbers to the right or more equal to it - returns the index of such an element in the array. I highly recommend you solve this problem yourself. Both procedures (Lomuto and Hoar) given on Wikipedia work well.
• Once you are sure that your partitioning works as expected, you recursively sort the two partitions using the same qsort procedure (the order of the recursive calls doesn't matter) , and you're done !

I tried to execute the partition procedure myself:

 /** Implements partitioning of array a from a[p] to a[r], leaves all the other elements of the array intact. @param a the given int array @param p int first index of the part of array to be partitioned @param r int the second index of the part of array to be partitioned */ public static int partition(int[] a, int p, int r) { //this is something I have written int pivot = a[p]; int i = p + 1; int j = i - 1; while (i <= r) { if (a[i] < pivot) { a[j] = a[i]; a[i] = a[j+1]; j++; } i++; } a[j] = pivot; return j; } private static void swap(int[] ints, int i1, int i2) { int tmp = ints[i2]; ints[i2] = ints[i1]; ints[i1] = tmp; } 

Now I have not proved the correctness of this procedure, but we can do it separately. You can even override the Lomuto procedure and make sure that it works to your satisfaction.

What is it. If you want to debug this with a debugger, you can more than do it. Here's the whole implementation .

Now the question of converting this recursive procedure to iterative is very interesting, and this document: (shameless plugin: I wrote it) http://bit.ly/recurse-iterate should give you some tips . The actual conversion of the Quicksort procedure above to an iterative version remains as an exercise for the reader :-).