Asymptotic distribution theory for Hoare's selection algorithm

1 March 1996

journal article
general applied-probability
Published by Cambridge University Press (CUP) in Advances in Applied Probability

Vol. 28 (01) , 252-269
https://doi.org/10.1017/s000186780002735x

Abstract

We investigate the asymptotic behaviour of the distribution of the number of comparisons needed by a quicksort-style selection algorithm that finds thelth smallest in a set ofnnumbers. Lettingntend to infinity and considering the valuesl =1, ···,nsimultaneously we obtain a limiting stochastic process. This process admits various interpretations: it arises in connection with a representation of real numbers induced by nested random partitions and also in connection with expected path lengths of a random walk in a random environment on a binary tree.

Keywords

This publication has 7 references indexed in Scilit:

Probability metrics and recursive algorithms
Advances in Applied Probability, 1995
A fixed point theorem for distributions
Stochastic Processes and their Applications, 1992
A limit theorem for “quicksort”
RAIRO - Theoretical Informatics and Applications, 1991
Exponential bounds for the running time of a selection algorithm
Journal of Computer and System Sciences, 1984
Some Asymptotic Theory for the Bootstrap
The Annals of Statistics, 1981
Quicksort
The Computer Journal, 1962
Algorithm 64: Quicksort
Communications of the ACM, 1961