Paper Info
Title
Distributional analysis of swaps in Quick Select
Abstract
We investigate the number of swaps made by Quick Select (a variant of Quick Sort for finding order statistics) to find an element with a randomly selected rank under realistic partition algorithms such as Lomuto's or Hoare's. This kind of grand average provides a smoothing over all individual distributions for specific fixed order statistics. The grand distribution for the number of swaps (when suitably scaled) is a perpetuity (a sum of products of independent mixed continuous random variables supported on the interval (0,1)). The tool for this proof is contraction in the Wasserstein metric space, and identifying the limit as the fixed-point solution of a distributional equation. The same methodology carries over when Quick Select is commissioned to find an extremal order statistic (of a relatively small or relatively large rank) and the results are of similar nature. It is one of our purposes to show that analysis under different partition algorithms leads to different results.
Year
DOI
Venue
2010
10.1016/j.tcs.2010.01.029
Theor. Comput. Sci.
Keywords
DocType
Volume
Average-case analysis,order statistic,different partition algorithm,Grand average,grand distribution,extremal order statistic,Combinatorial probability,Algorithm,Recurrence,Quick Select,specific fixed order statistic,Sorting,Perpetuity,Distributional analysis,Quick sort,different result,large rank,grand average,Quick Sort
Journal
411
Issue
ISSN
Citations 
16-18
Theoretical Computer Science
1
PageRank 
References 
Authors
0.35
5
1
Name
Order
Citations
PageRank
Hosam M. Mahmoud118355.63