|
In the previous page,
we made our first recursive call to the quicksort function.
Much of what you will see in this page is a repeat of what
you saw in earlier pages, but be sure to take note of the
range of the values you are checking this time around.
We enter our main loop, for i (1) is less than or equal to
j
(3). With that initial hurdle passed, we now have to deal
with the two inner left and right loops:
The left loop
checks to see if the value at index position i is less than
the pivot value, 4. Of course array[i] is 7, and 7 is not less
than 4. The left loop ends. The right loop checks to see if
array[j] is greater than the
pivot value. This too proves to be false, because array[j] is 2
and the pivot value is 4. This loop also ends after the
first try! So after all this, the value of i is
still 1, and the value of j is still 3:
The values for i and j fit the condition for the if
statement block (the pseudocode in pink) that checks if i
is less than or equal to j. It
is time to swap the array values referenced at i and j. Like
before, a temporary variable is created to store the value from
array[i], array[i] is set to the value of array[j], and
array[j] is set to the value stored
by the temp variable. Before we forget, remember that
the i variable is incremented by 1 and the j
variable is decremented by 1.
Everything is sorted! Congrats? Well, it is a bit too
early to celebrate, for Flash does not have a way of knowing
whether an array is sorted or not. It will continue to
proceed through the various loops until the code simply has
nowhere to go as you will see.
As mentioned above, the value of i is now 2, and the value
of j is also 2. We enter the main for loop, and since i <=
j, we proceed to the left-sided loop. The pivot value is 4,
and the array[i] is also 4, so the loop breaks because
array[i] is not less than the pivot value. So, we break out
of this loop and go to the right-sided loop. Is array[j]
greater than the pivot? No, for array[j] is also 4, and 4 is
not greater than 4.
We now enter the section of code responsible for swapping
the values. First we check to make sure that the value of i
is less than or equal to the value of j, and that is true
because i and j are both 2. The swap proceeds as before, but
notice that you are swapping the same value! Both the
array[i] and array[j] refer to the value 4, and swapping
them does not do anything at all. But, what does happen due
to the swap function, is that the i variable is incremented
by 1 and the j variable is decremented by 1:
We are almost done with this walkthrough. Let's continue to
the next page!
|
Fast Sorting with Quicksort
