ANALYSIS OF SWAPS IN RADIX SELECTION

作者：Elmasry Amr^*; Mahmoud Hosam

来源：Advances in Applied Probability, 2011, 43(2): 524-544.

DOI：10.1239/aap/1308662491

• Random structure
• algorithm
• order statistic
• recurrence
• perpetuity
• phase change
• digital data
• digital sorting
• selection
• Mellin transform
• poissonization
• depoissonization

Radix Sort is a sorting algorithm based on analyzing digital data. We study the number of swaps made by Radix Select (a one-sided version of Radix Sort) to find an element with a randomly selected rank. This kind of grand average provides a smoothing over all individual distributions for specific fixed-order statistics. We give an exact analysis for the grand mean and an asymptotic analysis for the grand variance, obtained by poissonization, the Mellin transform, and depoissonization. The digital data model considered is the Bernoulli (p). The distributions involved in the swaps experience a phase change between the biased cases (p not equal 1/2) and the unbiased case (p = 1/2 In the biased cases, the grand distribution for the number of swaps (when suitably scaled) converges to that of a perpetuity built from a two-point distribution. 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. In the unbiased case the same scaling for the number of swaps gives a limiting constant in probability.

• 出版日期2011-6