Details
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 252-269 |
| Seitenumfang | 18 |
| Fachzeitschrift | Advances in applied probability |
| Jahrgang | 28 |
| Ausgabenummer | 1 |
| Publikationsstatus | Veröffentlicht - März 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.
ASJC Scopus Sachgebiete
- Mathematik (insg.)
- Statistik und Wahrscheinlichkeit
- Mathematik (insg.)
- Angewandte Mathematik
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: Advances in applied probability, Jahrgang 28, Nr. 1, 03.1996, S. 252-269.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › 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 -