|
Continuing from the previous
page, remember, the value of i is 1. The loop
condition was to ensure that i is less than or equal to
j, and that is no longer true. So, we break out of the main loop
indicated by the blue region in our pseudocode and proceed
to the two if statements:
The questions the two if statements ask are:
- Is the value of our left variable less than
j?
- Is the value of our right variable greater than
i?
For the first condition, our left variable is 0, and that
is not less than j
which also has a value of 0. The left
variable is is only equal to the j variable, so this
condition fails. The second if statement, though, passes for the value of our
right variable is 3, and i is 1. What this
basically signifies is that
our right side, the portion to the right of i,
still requires some organization.
So what we do now is call our quicksort function ON JUST
the values between i and the array value at
the index position stored by the right
variable. We don't do anything to the
values to the left of i, for we assume it
is already sorted:
And this
brings us to an important property of quicksort. Every time
the quickSort function is called recursively, only a subset
of the data is passed in to the function again. In other
words, the quicksort function does less and less work as it
keeps getting called, because the size of the array it is
working with gets smaller.
So we now call our quicksort function again, except as
determined by the if statement earlier, we only look at the
last three values of our array. The quickSort
function call looks as follows:
The code representation is as follows quickSort(array,
i, right) where i is 1 and right is 3.
This is still only the function call. Once you enter the
quickSort function, you assign values to your i and
j variables along with the pivot variable:
That corresponds to, i equaling 1,
j equaling 3, right equaling 3, array[i]
equaling 7, array[j] equaling 2, and the pivot
value equaling 4 for the middle value of the values of [7,
4, 2] is 4.
Great, so now we pretty much repeat what we did earlier,
and that will be covered on the
next page.
|
Fast Sorting with Quicksort
