Implementation and Analysis of Quicksort
Quicksort works fundamentally by recursively partitioning an unsorted set of elements until all
partitions contain a single element. In the implementation presented
data initially contains the unsorted
size elements stored in a single
block of contiguous storage. Quicksort sorts in place, so all
partitioning is performed in
data as well.
When qksort returns,
data is completely sorted.
As we have seen, an important part of quicksort is how we
partition the data. This task is performed in the function
partition (see Example
12.2) . This function partitions the elements between
i is less than
We begin by selecting a partition value using the
median-of-three method mentioned earlier. Once the partition value has
been selected, we move from
k to the left
data until we find an element that is
less than or equal to it. This element belongs in the left partition.
Next, we move from
i to the right until we
find an element that is greater than or equal to the partition value.
This element belongs in the right partition. Once two elements are
found in the wrong partition, they are swapped. We continue in this
k cross. (You may want to consider how we
know that if any one element is in the wrong partition, there is
always one that can be swapped with it.) Once
k cross, all elements to the left of the partition value are less than or equal to it, and all elements to the right are ...