Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
On Smoothed Analysis of Quicksort and Hoare’s Find
| |
|
On Smoothed Analysis of Quicksort and Hoare’s Find
Mahmoud Fouz17  , Manfred Kufleitner18 , Bodo Manthey17 and Nima Zeini Jahromi17
| (17) |
Department of Computer Science, Postfach 151150, Saarland University, 66041 Saarbrücken, Germany |
| (18) |
Universität Stuttgart, FMI, Universitätsstraße 38, 70569 Stuttgart, Germany |
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 Θ( n
2), the average-case number is Θ( n). 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 of [0,1], and then each number is perturbed by adding a random number drawn from the interval [0, d]. We prove that Hoare’s find needs  comparisons in expectation if the adversary may also specify the element that we would like to find. Furthermore, we show
that Hoare’s find needs fewer comparisons for finding the median.
In the second model, each element is marked with probability p and then a random permutation is applied to the marked elements. We prove that the expected number of comparisons to find
the median is in  , which is again tight.
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.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|