Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-06T14:29:34.658Z Has data issue: false hasContentIssue false
  • English
  • Français

Quickselect and the Dickman Function

Published online by Cambridge University Press:  06 September 2002

HSIEN-KUEI HWANG  and
TSUNG-HSI TSAI
HSIEN-KUEI HWANG
Affiliation:
Institute of Statistical Science, Academia Sinica, Taipei 115, Taiwan (e-mail: hkhwang@stat.sinica.edu.tw)
TSUNG-HSI TSAI
Affiliation:
Institute of Statistical Science, Academia Sinica, Taipei 115, Taiwan (e-mail: hkhwang@stat.sinica.edu.tw)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We show that the limiting distribution of the number of comparisons used by Hoare's quickselect algorithm when given a random permutation of n elements for finding the mth-smallest element, where m = o(n), is the Dickman function. The limiting distribution of the number of exchanges is also derived.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 11 , Issue 4 , July 2002 , pp. 353 - 371
Copyright
2002 Cambridge University Press