|
Let's pick up from where we left off in the
previous page. When it reaches a number that is
not greater than the pivot value, for example as shown in
the above image, then the variable j stops in its tracks. So
you now have both the i and j variables referencing array
values that are on the wrong side of our pivot value:
The left pointer stopped at 16, because 16 is not
smaller than our pivot value 10. The right pointer
stopped at 3, because 3 is not greater than our pivot
value of 10. So what happens next? You swap those values! The
number 3 will occupy the spot used by the number 16, and the
number 16 will find itself at the spot used by the number 3:
Your left and right pointers increment in their
respective directions also and continue the above steps -
stopping and swapping wrong values:
The swapping action saves computation time by not having
to guess (or calculate!) where to place the incorrect value.
By finding an incorrect value on either side of the pivot,
we automatically know that by swapping those two values, we
are now placing both values into their appropriate side of
the pivot.
Onwards to the next page!
|
Fast Sorting with Quicksort
