On smoothed analysis of quicksort and Hoare's find
Fouz, Mahmoud and Kufleitner, Manfred and Manthey, Bodo and Zeini Jahromi, Nima (2012) On smoothed analysis of quicksort and Hoare's find. Algorithmica, 62 (34). pp. 879905. ISSN 01784617

PDF
966kB 
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 or onesided quicksort  is an easytoimplement algorithm for finding the kth smallest element of a sequence. While the worstcase number of comparisons that Hoare’s find needs is Theta(n^2), the averagecase number is Theta(n). We analyze what happens between these two extremes by providing a smoothed analysis. In the first perturbation model, an adversary specifies a sequence of n numbers of [0,1], and then, to each number of the sequence, we add a random number drawn independently from the interval [0,d]. We prove that Hoare's find needs Theta(n/(d+1) sqrt(n/d) + n) comparisons in expectation if the adversary may also specify the target element (even after seeing the perturbed sequence) and slightly fewer comparisons for finding the median. In the second perturbation model, each element is marked with a probability of 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 Omega((1−p)n/p log n). Finally, we provide lower bounds for the smoothed number of comparisons of quicksort and Hoare’s find for the medianofthree 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 medianofthree does not yield a significant improvement over the classic rule. 
Item Type:  Article 
Additional information:  Open Access 
Copyright:  © 2011 The Author(s) 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/79202 
Official URL:  http://dx.doi.org/10.1007/s0045301194909 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page