Multiple quickselect - Hoare's find algorithm for several elements
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
This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)