On Smoothed Analysis of Quicksort and Hoare's Find

Simple item page
dc.creatorFouz, Mahmoud
dc.creatorKufleitner, Manfred
dc.creatorManthey, Bodo
dc.creatorJahromi, Nima Zeini
dc.date2009-04-24
dc.date2009-04-25
dc.date.accessioned2026-07-07T13:08:30Z
dc.date.available2026-07-07T13:08:30Z
dc.descriptionWe 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. Moreover, 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.
dc.descriptionTo be presented at the 15th Int. Computing and Combinatorics Conference (COCOON 2009)
dc.identifierhttps://arxiv.org/abs/0904.3898
dc.identifierhttp://arxiv.org/abs/0904.3898
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/228436
dc.subjectData Structures and Algorithms
dc.subjectF.2.2
dc.titleOn Smoothed Analysis of Quicksort and Hoare's Find
dc.typetext

Files

Collections

arXiv