On smoothed analysis of quicksort and hoare's find

Abstract

We provide a smoothed analysis of Hoare's find algorithm and we revisit the smoothed analysis of quicksort.

Hoare's find algorithm - often called quickselect - is an easy-to-implement algorithm for finding the k-th smallest element of a sequence. While the worst-case number of comparisons that Hoare's find needs is quadratic, the average-case number is linear. We analyze what happens between these two extremes by providing a smoothed analysis of the algorithm in terms of two different perturbation models: additive noise and partial permutations.

In the first model, an adversary specifies a sequence of n numbers in the interval [0,1], and then each number is perturbed by adding a random number drawn from the interval [0,d]. In this setting, we give a tight bound for the number of comparisons in expectation of Hoare's find algorithm if the adversary may also specify the element that we would like to find. Furthermore, we consider the number of comparisons for finding the median. Again, we give tight bounds for the number of comparison in expectation.

In the second model, each element is marked with probability p and then a random permutation is applied to the marked elements. We also provide a tight bound for the expected number of comparisons for this second model.

Finally, we provide lower bounds for the smoothed number of comparisons of quicksort and Hoare's find for the median-of-three pivot rule, which usually yields faster algorithms than always selecting the first element: The pivot is the median of the first, middle, and last element of the sequence. We show that median-of-three does not yield a significant improvement over the classic rule: the lower bounds for the classic rule carry over to median-of-three.