next up previous contents index Search
Next: Picking a Pivot Up: 0.3 Sorting Algorithms Previous: 0.3 Sorting Algorithms

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.

Scott Gasch