|
As mentioned earlier, items on the right side are
guaranteed to be larger than items on the left side, and
items on the left side are guaranteed to be smaller than
items on the right side. This condition for the left and right elements holds
no matter how many divisions you go through. This
ensures that, in the end, you are going to have a collection
of data that is properly sorted. This probably sounds very
confusing, but don't
worry, just accept what I wrote as plausible for now, and
you will see by the end of the tutorial why it works out in
the end.
Now that you have a vague idea of how quicksort works,
let's look at its implementation. You learned about the
pivot value, but I did not explain how the sorting actually
works. In my example, I simply showed smaller numbers moving
to the left of the pivot, and numbers larger than the pivot
finding their way to the right side. How it actually works
is very useful to look at.
For any input, this time let's user real numbers, you have your pivot value, but you also
have two index variables i and j that set both the left boundary of
your input and the right boundary of your input:
What we want to do is ensure numbers to the left our
pivot value - 10 - are less than that value. Likewise, all
numbers to the right of the pivot value should be larger
than 10. So, the index pointer at the left moves right looking at each
value and asking, "Is the array value I am at right now less than
the pivot value?"
If the answer is yes, it proceeds to the next number:
This process of checking and moving right repeats until
the value at position i becomes greater than
our pivot value. When that happens, the i index variable
stops moving right (incrementing) and waits:
In a similar, yet opposite way, the index pointer at the
right decreases and moves left. At each position, it asks,
"Is the array value at j greater than the pivot value?"
If the current value at j is
indeed greater, the j variable decrements by one and proceeds left to the next number and asks
itself the same question:
Let's continue onto the next
page for the rest of the explanation.
|
Fast Sorting with Quicksort
