In:
Advances in Applied Probability, Cambridge University Press (CUP), Vol. 43, No. 02 ( 2011-06), p. 524-544
Abstract:
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 ≠ ½) and the unbiased case ( p = ½). 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.
Type of Medium:
Online Resource
ISSN:
0001-8678
,
1475-6064
DOI:
10.1017/S0001867800004973
Language:
English
Publisher:
Cambridge University Press (CUP)
Publication Date:
2011
detail.hit.zdb_id:
1474602-5
Permalink