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)