Name
Abstract | ||
|---|---|---|
We show that the limiting distribution of the number of comparisons used by Hoare's quick- select algorithm when given a random permutation of n elements for nding the m-th smallest element, where m = o(n), is the Dickman function. The limiting distribution of the number of exchanges is also derived. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1017/S0963548302005138 | Combinatorics, Probability & Computing |
Keywords | DocType | Volume |
dickman function,random permutation,quickselect algorithm,mth-smallest element,n element | Journal | 11 |
Issue | ISSN | Citations |
4 | 0963-5483 | 17 |
PageRank | References | Authors |
1.26 | 11 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hsien-Kuei Hwang | 1 | 365 | 38.02 |
| Tsung-Hsi Tsai | 2 | 81 | 8.20 |