%Information Proc. Letters
\input amstex
\documentstyle{amsppt}
\magnification=\magstep1
\font\sc=cmcsc10
\def\heute{\ifcase\month\or January\or February\or March\or April\or May
\or June\or July\or August\or September\or October
\or November\or December\fi
\space\number\day, \number\year}
\redefine\eps{\varepsilon}
\define\C{\Cal C}\redefine\P{\Cal P}
\NoBlackBoxes
\hfuzz=10pt
\headline={\hfil\folio\hfil}
\footline={\hfil}
\topmatter
\title
multiple quickselect --- \\
hoare's find algorithm for several elements
\endtitle
\author Helmut Prodinger \endauthor
\affil
Department of Algebra and Discrete Mathematics \\
Technical University of Vienna, Austria
\endaffil
\address
\flushpar
TU Vienna
\newline Wiedner Hauptstrasse 8--10
\newline A-1040 Vienna
\newline Austria
\endaddress
\email proding\@rsmb.tuwien.ac.at
\endemail
\thanks File: lint3.tex \endthanks
\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.
\endabstract
\endtopmatter
\def\gkp{1}
\def\gk{2}
\def\hoare{3}
\def\kmp{4}
\def\knu{5}
\def\knuifip{6}
\def\lenmah{7}
\def\mamosmy{8}
\def\serf{9}
\document
\centerline{--- \heute\ ---}
\vskip 1 cm
\head 1. Introduction \endhead
Hoare's {\sc Find} algorithm \cite{\hoare} uses the idea of {\sl Quicksort}
\cite{\knu} in order to select the $j$th element of a file of $n$ elements.
In each partitioning step, a certain element will be brought into its
correct position $k$.
In the process, elements are moved---those brought to the left of it
are smaller, and those brought to the right are larger.
If $k=j$, the element is found; if $kj$, one has to continue
on the left side, still searching for the $j$th element.
Two parameters are of interest: the (average) number of passes
(recursive calls) $P[n;j]$ and the (average) number of comparisons
$C[n;j]$. In Knuth's book \cite{\knu} we already find the values
$$
P[n;j]=H_{j}+H_{n+1-j}-1
$$
and
$$
C[n;j]=2\Big(n+3+(n+1)H_n-(j+2)H_j-(n+3-j)H_{n+1-j}\Big)
$$
where $H_n=1+\frac12+\dots+\frac1n$ denotes the $n$th harmonic number;
compare also \cite{\knuifip}
and \cite{\mamosmy}.
In \cite{\kmp}, this analysis was extended to the case of median--of--three
partitioning.
Hoare's idea can be extended as follows: Assume that we
simultaneously search for the $p$ elements with ranks
$j_1,j_2,\dots,j_p$
where $1\le j_1