Quickselect and the Dickman Function

HSIEN-KUEI HWANG, TSUNG-HSI TSAI

Source record

Source: Crossref

Published: Jul 1, 2002

DOI: 10.1017/s0963548302005138

Open original source ↗

Source abstract

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 m th-smallest element, where m = o ( n ), is the Dickman function. The limiting distribution of the number of exchanges is also derived.

Evidence graph

No public relationships recorded yet.

Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.