0.3.1 The Quicksort
Over the years computer scientists have come up with many different
algorithms for sorting data. C.A.R. Hoare's Quicksort, however, is
generally regarded as the most efficient and fastest sorting algorithm
in the average case. As we will see, though, a worst case data set
causes the Quicksort to perform poorly.
A Quicksort operates by selecting a value called the pivot point
and then arranging the data being sorted such that all data items with
a key value less than the that of the pivot point appear at the
beginning of the data structure and all data items greater than or
equal to the pivot value are moved towards the end of the data
structure.
Thus, the data set to be sorted is partitioned into two pieces;
the k items less in value than the pivot item's value, and the (n -
k) items greater than or equal to the pivot value. It is essential
to note that neither of these two partitions are sorted as they are
built; all we know after the partitioning operation is that every item
to the ``left'' of the pivot is less in value than it, and every item
``right'' of the pivot point is greater than or equal to it.
The Quicksort continues, at this point, to process the two partitions
discussed above. In each sub-partition a new pivot value is selected
which allows yet another sub-division of the data set. This process
of selecting a new pivot value and then sub-dividing a range of data
into two more partitions continues again and again until the size of a
resulting partition becomes small enough that it can be easily
explicitly sorted. This point usually occurs when there are two or
fewer items remaining in a partition because such ranges can be easily
put into order with a very little effort. As we will see later, there
are other alternatives.
| 
Search