Details
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 36-45 |
| Seitenumfang | 10 |
| Fachzeitschrift | Journal of applied probability |
| Jahrgang | 35 |
| Ausgabenummer | 1 |
| Publikationsstatus | Veröffentlicht - 1 Jan. 1998 |
Abstract
We obtain bounds for the distribution of the number of comparisons needed by Hoare’s randomized selection algorithm FIND and give a new proof for Grübel and Räsler’s (1996) result on the convergence of this distribution. Our approach is based on the construction and analysis of a suitable associated Markov chain. Some numerical results for the quantiles of the limit distributions are included, leading for example to the statement that, for a set S with n elements and n large, FIND will need with probability 0.9about 4.72 × n comparisons to find the median of S.
ASJC Scopus Sachgebiete
- Mathematik (insg.)
- Statistik und Wahrscheinlichkeit
- Mathematik (insg.)
- Entscheidungswissenschaften (insg.)
- Statistik, Wahrscheinlichkeit und Ungewissheit
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: Journal of applied probability, Jahrgang 35, Nr. 1, 01.01.1998, S. 36-45.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › Peer-Review
}
TY - JOUR
T1 - Hoare's Selection Algorithm
T2 - A Markov Chain Approach
AU - Grübel, Rudolf
PY - 1998/1/1
Y1 - 1998/1/1
N2 - We obtain bounds for the distribution of the number of comparisons needed by Hoare’s randomized selection algorithm FIND and give a new proof for Grübel and Räsler’s (1996) result on the convergence of this distribution. Our approach is based on the construction and analysis of a suitable associated Markov chain. Some numerical results for the quantiles of the limit distributions are included, leading for example to the statement that, for a set S with n elements and n large, FIND will need with probability 0.9about 4.72 × n comparisons to find the median of S.
AB - We obtain bounds for the distribution of the number of comparisons needed by Hoare’s randomized selection algorithm FIND and give a new proof for Grübel and Räsler’s (1996) result on the convergence of this distribution. Our approach is based on the construction and analysis of a suitable associated Markov chain. Some numerical results for the quantiles of the limit distributions are included, leading for example to the statement that, for a set S with n elements and n large, FIND will need with probability 0.9about 4.72 × n comparisons to find the median of S.
KW - Convergence in distribution
KW - Markov chains
KW - Randomized algorithms
KW - Stochastic ordering
UR - http://www.scopus.com/inward/record.url?scp=85037205177&partnerID=8YFLogxK
U2 - 10.1239/jap/1032192549
DO - 10.1239/jap/1032192549
M3 - Article
AN - SCOPUS:85037205177
VL - 35
SP - 36
EP - 45
JO - Journal of applied probability
JF - Journal of applied probability
SN - 0021-9002
IS - 1
ER -