Quicksort with Equal Keys

Abstract

This paper considers the problem of implementing and analyzinga Quicksortprogram when equal keys are likely to be present in the file to be sorted. Upper and lowerbounds are derivedon the average number of comparisons needed by any Quicksortprogramwhenequal keys are present. It is shown that, of the three strategies which have been suggested for dealing with equal keys, the method of always stopping the scanning pointers on keys equal to the partitioning element performs best. Introduction. The Quicksort algorithm, which was introduced by C. A. R. Hoare in 1960 (6), (7), has gained wide acceptance as the most efficient general-purpose sorting method suitable for useon computers. The algorithmhas a rich history: many modifications have been suggested to improve its perfor- mance, and exact formulas have been derived describing the time and space requirements of the most important variants (7), (9), (14). Although most files to be sorted contain at least some equal keys and sorting programs must always deal withthem properly, it is generally considered reasona- ble to assume in the analysis that the keys are distinct. This assumption is fundamental to the analysis of nearly all sorting programs, and it is very often realistic. In any situation where the number of possible key values far exceeds the number of keys to be sorted, the probability that equal keys are present will be very small. However, if the number of possible key values is not large, or if there is some other information about the file which indicates that equal keys are likely to be present, then the performance of many sorting programs, including Quicksort, has not been carefully studied. The purpose of this paper, then, is to investigate the performance of Quicksort when equal keys are present. The following section describes the algorithm and its analysis for distinct keys. Next, lower and upper bounds are derived for the average number of comparisons taken when equal keys are present. Following that, we shall consider, from a practical standpoint, the problem of implementing a version of Quicksort to handle equal keys. Finallywe shall compare the various methods and discover which is the most useful in practical sorting applications.