Details
| Original language | English |
|---|---|
| Pages (from-to) | 252-269 |
| Number of pages | 18 |
| Journal | Advances in applied probability |
| Volume | 28 |
| Issue number | 1 |
| Publication status | Published - Mar 1996 |
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
- Asymptotic distribution, Order statistics, Random binary numbers, Random walk in a random environment, Stochastic algorithms
ASJC Scopus subject areas
- Mathematics(all)
- Statistics and Probability
- Mathematics(all)
- Applied Mathematics
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Advances in applied probability, Vol. 28, No. 1, 03.1996, p. 252-269.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Asymptotic distribution theory for Hoare's selection algorithm
AU - Grübel, Rudolf
AU - Rösler, Uwe
PY - 1996/3
Y1 - 1996/3
N2 - 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.
AB - 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.
KW - Asymptotic distribution
KW - Order statistics
KW - Random binary numbers
KW - Random walk in a random environment
KW - Stochastic algorithms
UR - http://www.scopus.com/inward/record.url?scp=0000267981&partnerID=8YFLogxK
U2 - 10.1017/S000186780002735X
DO - 10.1017/S000186780002735X
M3 - Article
AN - SCOPUS:0000267981
VL - 28
SP - 252
EP - 269
JO - Advances in applied probability
JF - Advances in applied probability
SN - 0001-8678
IS - 1
ER -