Asymptotic distribution theory for Hoare's selection algorithm
- 1 March 1996
- journal article
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 28 (1) , 252-269
- https://doi.org/10.2307/1427920
Abstract
We investigate the asymptotic behaviour of the distribution of the number of comparisons needed by a quicksort-style selection algorithm that finds the lth smallest in a set of n numbers. Letting n tend to infinity and considering the values l = 1, ···,n simultaneously 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 8 references indexed in Scilit:
- Probability metrics and recursive algorithmsAdvances in Applied Probability, 1995
- A fixed point theorem for distributionsStochastic 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 algorithmJournal of Computer and System Sciences, 1984
- Some Asymptotic Theory for the BootstrapThe Annals of Statistics, 1981
- Branching ProcessesPublished by Springer Nature ,1972
- QuicksortThe Computer Journal, 1962
- Algorithm 64: QuicksortCommunications of the ACM, 1961