Fast Sorting with Quicksort
       by kirupa | 11 July 2006

Step 3.5: Quick Recap
Much shifting and swapping went on in the previous three steps. As a quick recap, these are the important values that are stored in memory from calling our quickSort function:

left = 0;

right = 3;

i = 1, array[i] = 7;

j = 1; array[j] = 7;

pivot = 1;

The above values sound reasonable once you look at what happened, for prior to the swap, recall i was 0, and j was 2. After the swap, recall that i is incremented by 1 and j is decremented by 1. The pivot value had been 1 well before the swap, and it had not been changed since then. So even though our 1 value is not near the center of the array, our pivot value is still pointing to it. It's all good, for you will later see that the choice of the pivot point location is more of an optimization more so than a basic requirement for quicksort to work properly.

Step 4:
Alright, let's continue! Our i value is still less than or equal to the j value, so the loop continues again, and we are back in the blue portion of our pseudocode again:

For reference, this is where we are at in the array itself:

Is the array value at i less than the pivot point? No - 7 is not less than 1. We break out of this loop.

We now enter our for loop for the j variable. Is the array value at j greater than the pivot point? Yep! So we decrement j. The value of j is now 0:

Onwards to the next page!

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13