Multiple quickselect - Hoare's find algorithm for several elements
Abstract.
Hoare's Find algorithm can be used to select
$p$ specified order statistics
$j_1,j_2,\dots,j_p$ from a file of $n$ elements simultaneously.
We give precise formul\ae\ for both the average number of passes and
the average number of comparisons. Averaging again over all possible
subsets of $p$ elements, we get results of Lent and Mahmoud as
corollaries.
helmut@gauss.cam.wits.ac.za,
This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)