A generating functions approach for the analysis of grand averages for Multiple Quickselect

\begin{abstract} Hoare's Find algorithm can be used to select $p$ specified order statistics $j_1,\dots,j_p$ from a file of $n$ elements simultaneously. Averaging over all $\binom{n}{p}$ subsets of $\{1,\dots,n\}$ defines the grand averages of the number of passes and comparisons. We use a generating functions approach to compute averages and variances of these parameters. Additionally we sketch analogous developments for the instance of median-of-three partition and binary (Catalan) trees. \end{abstract}

• Tex
• Dvi
• PostScript