%
\documentclass[a4paper]{article}
\usepackage[centertags,reqno]{amstex}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% MACRO DEFINITIONS BEGIN HERE
%
% 
\makeatletter

\RequirePackage{theorem}

% \hierchenumerate tiene como efecto que los entornos 
% \begin{enumerate} ... \end{enumerate} de 2o y 3r nivel usen 
% etiquetas del tipo 1.3 o 2.1.5

\newcommand{\hierchenumerate}{
\newcommand{\theenumii}{\arabic{enumii}}
\newcommand{\theenumiii}{\arabic{enumiii}}
\newcommand{\labelenumii}{\theenumi.\theenumii}
\newcommand{\labelenumiii}{\theenumi.\theenumii.\theenumiii}}


% Definicion de varios entornos theorem-like: theorem, lemma,
% corollary, proposition, ...
% Escribir al comienzo del documento: \definetheorems

\newcommand{\definetheorems}{
% define las etiquetas para poder cambiarlas facilmente
\newcommand{\theoremname}{Theorem}
\newcommand{\lemmaname}{Lemma}
\newcommand{\corollaryname}{Corollary}
\newcommand{\propositionname}{Proposition}
\newcommand{\definitionname}{Definition}
\newcommand{\conjecturename}{Conjecture}
\newcommand{\claimname}{Claim}

\newtheorem{theorem}{\theoremname}[section]
\newtheorem{lemma}{\lemmaname}[section]
\newtheorem{corollary}{\corollaryname}[section]
\newtheorem{proposition}{\propositionname}[section]
\newtheorem{defn}{\definitionname}[section]
\newtheorem{conjecture}{\conjecturename}[section]
\newtheorem{claim}{\claimname}[section]
}

% Entorno para demostraciones de teoremas, lemas, etc.
% \begin{proof} ... \end{proof} actua de forma similar a un entorno
% theorem-like sin numeracion, escribe Proof en boldface, 
% el texto se escribe en \rm y se pone un simbolo q.e.d.
% \begin{refpf} ... \end{refpf} es igual que el entorno 'proof'
% pero pone de modo automatico referencia al teorema, lema, ... mas
% recientemente enunciado (del cual se supone se esta dando la
% demostracion)
 
\providecommand{\qed}{\ensuremath{\thinspace \raisebox{0.1cm}{\fbox{}} \thinspace}}
\newenvironment{proof}{\begin{trivlist} \item[\hskip \labelsep{\bfseries
\proofname.}]\setlength{\parindent}{0pt}}{\qed\end{trivlist}}

\newenvironment{refproof}{\begin{trivlist} \item[\hskip \labelsep{\bfseries
\proofname\ (\of \box0~\box1)}]}{\qed\end{trivlist}}

\providecommand{\proofname}{Proof}
\providecommand{\of}{of\ }

% Entorno para definicion por casos: usar en modo matematico

\newenvironment{defcases}{\left\{\begin{array}{ll}}{\end{array}\right.}

% Acknowledgements
% Entorno para escribir agradecimientos; similar al entorno abstract
% \begin{ackno} We thank Menganito Smith for ... \end{ackno}

\newcommand{\ackno}{\section*{\acknoname}}
\newcommand{\acknoname}{Acknowledgements}
\def\endackno{\par}

% Entorno para ``excursiones'': comentarios, material de tipo
% marginal o avanzado, etc. (idea original de J.L. Balcazar, en su
% libro ``Programacion Metodica'')
% \begin{excursion} ... \end{excursion} escribe el texto en una fuente
% menor (footnotesize), con margenes mas amplios (quotation) y
% delimitado por corchetes dobles [[ ... ]]

\newcommand{\bcomm}{\ensuremath{[\![}}
\newcommand{\ecomm}{\ensuremath{]\!]}}
\newenvironment{excursion}{%
\begin{quotation}\bcomm\footnotesize}{\ecomm\end{quotation}}

% Inclusion condicional de ficheros (p.e. figuras en PiCTeX). 
% Hay otros mecanismos posibles que
% son en muchos casos mas adecuados de usar que este.
%
% El mecanismo se basa en tres macros:
% 1- \includeimage{<fichero>}{<longitud>} sirve para incluir el
% fichero cuyo nombre se da o dejar el espacio vertical 
% indicado por el segundo parametro
% 2- \incimages activa las inclusiones de ficheros
% 3- \dontincimages inactiva las inclusiones y en cada \includeimage
% se deja un espacio vertical de la longitud especificada

\newif\ifinclimage
\newcommand{\incimages}{\inclimagetrue}
\newcommand{\dontincimages}{\inclimagefalse}
\newcommand{\includeimage}[2]{\ifinclimage
{\begin{center}
\mbox{\input{#1}}
 \end{center}
}
\else
\vspace{#2}\fi}

% Simbolos matematicos: abreviaturas, operadores frecuentes, etc.
%
% 
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}

\newcommand{\pordef}{\mathbin\overset{\text{def}}{=}}	   % por definicion
\newcommand{\img}{\text{i}}		   		   % i = (-1)^(1/2)
\newcommand{\stirfk}[2]{\fracwithdelims[][0pt]{#1}{#2}}    % numero de Stirling
							   % primera especie
\newcommand{\stirsk}[2]{\fracwithdelims\{\}[0pt]{#1}{#2}}  % numero de Stirling
							   % segunda especie
\newcommand{\ffact}[2]{#1^{\underline{#2}}}                % falling factorial
\newcommand{\rfact}[2]{#1^{\overline{#2}}}		   % raising factorial

\newcommand{\Res}{\mathop{\textrm{Res}}\nolimits}   % Residuo
\newcommand{\Exp}{\mathop{\textrm{E}}\nolimits}	    % E(X)
\newcommand{\Var}{\mathop{\textrm{Var}}\nolimits}   % Var(X)
\newcommand{\Prob}{\mathop{\textrm{Prob}}\nolimits} % Prob
\newcommand{\bigOh}{\mathop{\mathcal{O}}\nolimits}  % O-grande


\newcommand{\almostall}{\hbox{\rlap{$_{\thinspace\forall}$}{$^{^\infty}$}}}
\newcommand{\infoften}{\hbox{\rlap{$_{\thinspace\exists}$}{$^{^\infty}$}}}

% Miscelanea

\newcommand{\LuO}{\text{$\Lambda$\kern-.1667em              % logotipo LuO
\lower.5ex\hbox{$\Upsilon$}\kern-.125em $\Omega$}}      

\newcommand{\trademark}{\ensuremath{^{%
\ooalign{\hfil\raise.05ex\hbox{\footnotesize R}\hfil\crcr\mathhexbox20D}}}}

\providecommand{\email}[1]{E-mail: \texttt{#1}}

%%%%%%%%%

\RequirePackage{fancyheadings}
\let\at=@
\let\oldtitle=\title
\let\oldauthor=\author
\renewcommand{\title}[2][The Title]{\newcommand{\@stitle}{#1}%
\oldtitle{%\normalfont\bfseries\LARGE 
\scshape #2}}
\renewcommand{\author}[2][T. A. Uthor]{\newcommand{\@sauthor}{#1}%
\oldauthor{\scshape #2}}
\renewcommand{\section}{\@startsection{section}{1}%
  \z@{.7\baselineskip\@plus\baselineskip}{.5\baselineskip}%
  {\normalfont\scshape\centering}}
\renewcommand{\subsection}{\@startsection{subsection}{2}%
  \z@{.5\baselineskip\@plus.7\baselineskip}{-.5em}%
  {\normalfont\bfseries}}
\renewcommand{\@seccntformat}[1]{\csname the#1\endcsname.\quad}

\pagestyle{fancy}
\lhead[]{\thepage}
\chead[\scshape\@stitle]{\scshape\@sauthor}
\rhead[\thepage]{}
\lfoot{} \cfoot{} \rfoot{}
\setlength{\headrulewidth}{0 pt}
\setlength{\footrulewidth}{0pt}


\newenvironment{myalign}%
{\setlength{\arraycolsep}{2pt}%
\begin{array}{rl}}%
{\end{array}}

\RequirePackage{float}
% New float type: algorithm
\floatstyle{ruled}
\newfloat{algorithm}{thp}{loa}
\floatname{algorithm}{Algorithm}

% COMMENT
\newcommand{\COMMENT}[1]{\ensuremath{\{\text{#1}\}}}
\newcommand{\kw}[1]{\text{\bfseries #1}}

% \begin{pcode} ... \end{pcode} 
%
% this environment is a slight modification of the tabbing environment.
% the specific characteristics are:
%  1) all lines are typeset in math mode
%  2) |<something>| prints <something> in \rm if issued inside math
%      mode (for instance, inside the environment);  
%      and in \sl if issued outside math mode
%  3) _ can be used instead of \_ inside the code environments and in
%     text; it produces subscripts in math mode as usual
%  5) <return>'s are obeyed; if you want to break lines in the source
%  but not in the final document terminate the line with a comment char %
%  6) you can leave a blank line using \\
%
% it also introduces a command \numberlines that has no effect in this
% environment, but it has in the *-form of code
% CUST: The macro \algofontsize allows 
% changing the size of the font for the text written inside the
% environment. Its default value is footnotesize.

\newcommand{\numberlines}{\relax}
\newcommand{\algofontsize}{\footnotesize}
\newcommand{\identinfont}{\upshape}
\newcommand{\identoutfont}{\slshape}
\newif\ifinsidecode
\insidecodefalse


\def\@programcr{$\@tabcr$}
{\catcode`\;=\active \gdef;{\semicolon\;}}
\mathchardef\semicolon="603B
\catcode`\_=\active \gdef_{\ifinsidecode\_\else\ifmmode\sb\else\_\fi\fi}


\catcode`\|=12\relax
\def\origbar{|}
\catcode`\|=\active

\def|{\ifx\@sharp\relax\origbar\else\@dovar\fi}
\def\@dovar#1#2|{#1\ifinsidecode{\mbox{\identinfont #2}}\else{\text{\identoutfont #2}}\fi} 


\def\@tabcommandson{% activate tabbing commands:
    % \tab sets a tab stop and adds one to the margin tab:
    \def\tab{$\=\+$}
    % Must finish current field before testing if at margin:
    \def\@finishfield{\@stopfield\@addfield\@startfield}
    % \untab removes one tab stop and moves left if at the beginning of a line:
    \def\untab{$\@finishfield\@ifatmargin\@ltab\else\relax\fi\-$}
    %\def\untab{$\-\<$}
    % \@marginspace adds an extra space unless there is no text on the line:
    \def\@marginspace{$\@finishfield$\@ifatmargin\relax\else\ \fi}}

\def\@tabcommandsoff{% deactivate tabbing commands:
    \let\tab=\relax
    \let\@finishfield=\relax
    \let\untab=\relax
    \let\@marginspace=\ % never at margin thus always a space
}
\@tabcommandsoff

\def\pcode{\algofontsize\numberlines\insidecodetrue
\@tabcommandson \obeycr
\lineskip \z@\let\>\@rtab\let\<\@ltab\let\=\@settab
     \let\+\@tabplus\let\-\@tabminus\let\t\tab\let\u\untab
\let\\=\@programcr 
\global\@hightab\@firsttab \global\@nxttabmar\@firsttab
\dimen\@firsttab\@totalleftmargin \global\@tabpush0
\global\@rjfieldfalse \trivlist
\item[]\if@minipage\else\vskip\parskip\fi
\setbox\@tabfbox\hbox{\rlap{\indent\hskip\@totalleftmargin
\the\everypar}}\def\@itemfudge{\box\@tabfbox}\@startline\ignorespaces
$\@gobblecr
}

\def\endpcode{\ifinsidecode $\@stopline%
\ifnum\@tabpush > 0 \@badpoptabs\fi\endtrivlist
\@tabcommandsoff
\insidecodefalse
\else
\endtrivlist\endgroup\filbreak
\fi
}



% \begin{pcode*} ... \end{pcode*} 
% 
% the *-form of code numbers sequentially each line of the code (lines
% are separated by \\'s)
% CUST: the label of each line can be easily changed, by redefining
% the macro \codelinelabel and/or the macro \thecodeline; the counter
% is codeline.

\newcounter{codeline}
\renewcommand{\thecodeline}{\arabic{codeline}}
\newcommand{\codelinelabel}{\thecodeline.\ \ }

\def\@ifeline{\ifdim \wd\@curline =\z@}
\def\@ifefield{\ifdim \wd\@curfield = \z@}

\@namedef{pcode*}{\def\numberlines{\setcounter{codeline}{0}
\def\@numstopline{%
\addtocounter{codeline}{1}
\unskip\@stopfield\if@rjfield \global\@rjfieldfalse
   \@tempdima\@totalleftmargin \advance\@tempdima\linewidth
\hbox to\@tempdima{\@itemfudge\codelinelabel\hskip\dimen\@curtabmar
   \box\@curline\hfil\box\@curfield}\else\@addfield
   \hbox{\@itemfudge\codelinelabel\hskip\dimen\@curtabmar\box\@curline}\fi}
\def\@nonumstopline{%
\unskip\@stopfield\if@rjfield \global\@rjfieldfalse
   \@tempdima\@totalleftmargin \advance\@tempdima\linewidth
\hbox to\@tempdima{\@itemfudge\hskip\dimen\@curtabmar
   \box\@curline\hfil\box\@curfield}\else\@addfield
   \hbox{\@itemfudge\hskip\dimen\@curtabmar\box\@curline}\fi}
\def\@elinestop{\@ifefield\@nonumstopline\else\@numstopline\fi}
\def\@stopline{\@numstopline
%\@ifeline\@elinestop\else\@numstopline\fi
}}\pcode}


\@namedef{endpcode*}{\endpcode}


% \noprettyprint make the environments above behave like verbatim; tt
% is used as font, spaces and newlines are obeyed, there are no
% special characters, etc.
% 
% the code* environment still numbers each line of code (including
% blank lines)


\begingroup \catcode `|=0 \catcode `[= 1
\catcode`]=2 \catcode `\{=12 \catcode `\}=12
\catcode`\\=12 |gdef|@xcode#1\end{pcode}[#1|end[pcode]]
|gdef|@sxcode#1\end{pcode*}[#1|end[pcode*]]
|endgroup

{\catcode`\^^M=\active % these lines must end with %
  \gdef\obeylines{\catcode`\^^M\active \def^^M{\par\numberlines}}%
  \global\let^^M\par} % this is in case ^^M appears in a \write

\def\noprettyprint{%
\def\@code{\noindent\footnotesize
\trivlist \item[]\if@minipage\else\vskip\parskip\fi
\leftskip\@totalleftmargin\rightskip\z@
\parindent\z@\parfillskip\@flushglue\parskip\z@
\@tempswafalse \def\par{\if@tempswa\hbox{}\fi\@tempswatrue\@@par}
\obeylines \tt \catcode``=13 \@noligs \let\do\@makeother \dospecials}
%
\def\pcode{\@code \frenchspacing\@vobeyspaces \@xcode}
\def\endpcode{\endtrivlist}
%
\@namedef{pcode*}{\setcounter{codeline}{0}%
\def\numberlines{\addtocounter{codeline}{1}\codelinelabel}%
\@code \frenchspacing\@vobeyspaces \@sxcode}
\expandafter\def\csname endpcode*\endcsname{\endtrivlist}}

\def\PROGRAM{\kw{pro}\tab\kw{gram\ }}
\def\ENDPROGRAM{\untab}
\def\TYPE{\kw{type}\ \tab}
\def\ENDTYPE{\untab}
\def\VAR{\kw{var}\ \tab}
\def\ENDVAR{\untab}
\def\CONST{\kw{const}\ \tab}
\def\ENDCONST{\untab}
\def\ARRAY{\kw{array}\ }
\def\RECORD{\tab\kw{rec}\tab\kw{ord}}
\def\ENDRECORD{\untab\kw{end}$\-$}
\def\BEGIN{\kw{beg}\tab\kw{in}}
\def\END{\untab\kw{end}}
\def\IF{\kw{if}\ }
\def\ELSE{\untab\kw{else}\ \tab}
\def\ENDIF{\untab\untab}
\def\THEN{\ \tab\kw{then}\ \tab}
\def\SKIP{\emptyset}
\def\WHILE{\kw{whi}\tab\kw{le}\ }
\def\ENDWHILE{\untab}
\def\DO{\kw{\ do}\ }
\def\ITERATE{\kw{do}\ \tab}
\def\ENDITERATE{\untab}
\def\FOR{\kw{for}\tab\ }
\def\ENDFOR{\untab}
\def\REPEAT{\kw{rep}\tab\kw{eat}\ }
\def\UNTIL{\untab\kw{until}\ }
\def\AND{\mathbin{\kw{and}}}
\def\OR{\mathbin{\kw{or}}}
\def\NOT{\mathop{\kw{not}}}
\def\OF{\kw{\ of\ }}
\def\IN{\kw{\ in\ }}
\def\DIV{\mathbin{\kw{div}}}
\def\MOD{\mathbin{\kw{mod}}}
\def\PROCEDURE{\kw{pro}\tab\kw{cedure\ }}
\def\ENDPROCEDURE{\untab}
\def\FUNCTION{\kw{fun}\tab\kw{ction\ }}
\def\ENDFUNCTION{\untab}
\def\RETURN{\kw{return\ }}
\def\INP{}
\def\OUT{\kw{var\ }}
\def\INOUT{\kw{var\ }}
\def\TO{\kw{\ to\ }}
\def\LEQ{\le}
\def\GEQ{\ge}
\def\NOTEQC{\not=}
\def\NOTEQP{\not=}

\newcommand{\passes}[2]{P_{{#1},{#2}}}
\newcommand{\pgfpasses}[2]{\mathbf{P}_{{#1},{#2}}(z)}
\newcommand{\dpgfpasses}[2]{\left.\dfrac{d}{dz}\pgfpasses{#1}{#2}\right\origbar_{z=1}}
\newcommand{\comp}[2]{C_{{#1},{#2}}}
\newcommand{\pgfcomp}[2]{\mathbf{C}_{{#1},{#2}}(z)}
\newcommand{\dpgfcomp}[2]{\left.\dfrac{d}{dz}\pgfcomp{#1}{#2}\right\origbar_{z=1}}
\newcommand{\comptot}[2]{T_{{#1},{#2}}}
\newcommand{\exchan}[2]{X_{{#1},{#2}}}
\newcommand{\gpasses}[1]{\mathcal{P}_{#1}}
\newcommand{\gcomp}[1]{\mathcal{C}_{#1}}
\renewcommand{\Q}{\mathcal{Q}}
\newcommand{\QF}{\Q_1}
\newcommand{\QS}{\Q_2}
\newcommand{\G}{\mathcal{G}}
\newcommand{\D}{\mathcal{D}}
%\def\poch#1#2{#1^{\underline{#2}}}
\makeatother

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% DOCUMENT STARTS HERE

\title[Analysis of Hoare's FIND Algorithm]%
{Analysis of Hoare's FIND Algorithm with Median--of--three Partition%
\thanks{This research was supported by the program Acciones Integradas
Hispano-Austr\'{\i}acas (Austrian-Spanish Scientific
Exchange Program). The second author was also supported by the ESPRIT
BRA Program of the EC under contract no. 7141, project ALCOM II.}}

\author[P. Kirschenhofer and C. Mart\'{\i}nez and H. Prodinger]%
{P. Kirschenhofer%
\thanks{Institut f\"ur Algebra und Diskrete Mathematik.
Technical University of Vienna.
Wiedner Hauptstra{\ss}e 8--10, A-1040 Vienna, Austria.
\email{\{kirsch,proding\}{\at}rsmb.tuwien.ac.at}}, 
C. Mart\'{\i}nez%
\thanks{Departament de 
Llenguatges i Sistemes Inform\`atics.
Polytechnical University of Catalonia.
Pau Gargallo 5, E-08028 Barcelona, Spain.
\email{conrado{\at}goliat.upc.es}},
and H. Prodinger$^\dagger$}

\theorembodyfont{\slshape}
\definetheorems

\begin{document}
\maketitle


\begin{abstract}
Hoare's \textsc{Find} algorithm can be used to select the $j$th element out of
a file of $n$ elements. It bears a remarkable similarity to Quicksort;
in each pass of the algorithm, a pivot element is used to split the
file into two subfiles, and recursively the algorithm proceeds with 
the subfile that
contains the sought element. As in Quicksort, different strategies for
selecting the pivot are reasonable. In this paper, we consider the
Median--of--three version, where the pivot element is chosen as the
median of a random sample of three elements. Establishing some
hypergeometric differential equations, we find explicit
formul{\ae} for both the average number of passes and comparisons.
We compare these results with the corresponding ones for the basic
partition strategy.
\end{abstract}

\section{Introduction}
\label{sec:introduction}

The problem of \textsl{selection} consists in finding the $j$th
smallest (or $j$th largest) element out of a given set of $n$
elements. Particular important cases are finding the minimum ($j=1$),
the maximum ($j=n$) or the median ($j=\lfloor (n+1)/2\rfloor$). 
The first reasonably efficient solution to this problem was
devised by Hoare~\cite{Hoare61} in the early 60's. 
Hoare's~\textsc{Find} algorithm has
expected linear running time and is based upon the same design principles
as the well-known sorting algorithm 
Quicksort, also by Hoare~\cite{Hoare62}. In fact,
\textsc{Find} has also been called Quickselect, One-sided Quicksort, and
the like.

Soon after Hoare's work and as today, many other solutions have been
proposed for the problem of selection. A closely related topic that has
attracted much interest is 
that of lower bounds for this problem, both for 
the average and worst-case number of
comparisons.
Here, we just mention the worst-case
$\bigOh(n)$ solution to find the median of $n$ elements, proposed by 
Blum, Floyd, Pratt, Rivest and Tarjan~\cite{BFPRT70} in 1973. The
reader may find a comprehensive list of references in Gonnet
and Baeza-Yates's \emph{Handbook}~\cite{handbook2} about the topic of selection.

Most of the solutions proposed so far, although better than Hoare's
algorithm on a theoretical basis, are not practical because they are
difficult to implement, the constant factors and hidden lower order 
terms are too large, some of them have been devised for the particular
instance of finding the median and
their generalization to arbitrary $j$ is difficult, etc. 
The simplicity, elegance and robustness of \textsc{Find} make
it the algorithm of choice for most practical situations, like
Quicksort for sorting.
The probability of large deviations from the expected performance of
\textsc{Find} is probably very small, and the lower order terms,
hidden constant factors, etc.\ of any reasonable implementation of the
algorithm are also quite small.

We now introduce the basic algorithm in detail (see Algorithm~\ref{algo:find}). 
We are given an array $A$ of $n>0$
items, and a rank $j$, $1\le j\le n$. For simplicity, we assume that
the elements of $A$ are integers. Since we are presenting a
recursive implementation, the procedure |find| operates in a segment $A[l:u]$
of the array, such that it must contain the sought element. The
first call to |find| is, obviously, $|find|(A,j,1,n)$.

\begin{algorithm}
\bigskip
\begin{pcode}
\COMMENT{$l \LEQ j \LEQ u$, $A[l:u]$ contains the $j$th smallest of $A[1:n]$ }

 \FUNCTION |find|(\INOUT A : \ARRAY [1..n] \OF |integer|; j, l, u :|integer|)
 \VAR r, k :|integer|; \ENDVAR 

 \BEGIN 
 \IF l = u \THEN \RETURN A[l]; \ENDIF 

    r := |select_pivot|(A, l, u);

    |swap|(A[l], A[r]);

\COMMENT{$A[l] = p$, $A[l:u]$ contains the $j$th element }

    |partition|(A, l, u, k);

\COMMENT{$\forall i:l\le i<k:A[i]\le p$, $A[k]=p$, and $\forall i:k<i\le u:A[i]>p$ }

 \IF j = k \THEN \RETURN A[k];
 \ELSE \IF j < k \THEN \RETURN |find|(A, j, l, k - 1);
 \ELSE \RETURN |find|(A, j, k + 1, u) \ENDIF %
 \ENDIF 
 \END %
\end{pcode}
\caption{\textsc{Find}}
\label{algo:find} 
\end{algorithm}

In order to select the $j$th smallest element, a certain
element of the given segment, 
the \textsl{pivot}, is brought into its correct position, left to it being
only smaller, right to it only larger elements. The index $r$ of the
pivot is computed by |select_pivot|. For the time being, we can assume
that this function returns a value between $l$ and $u$ at random. Then
the pivot is exchanged with $A[l]$ and the procedure |partition| is called.
After the partition, the segment $A[l:u]$ is divided into three parts:
the first one, $A[l:k-1]$, contains all elements smaller or equal to
the pivot; $A[k]$ contains the pivot; and $A[k+1:u]$ contains all
elements larger than the pivot
(see Algorithm~\ref{algo:partition}). Clearly, if $m$ is the number of
elements in the segment,
then $m-1$ comparisons are needed to determine the correct position of the
pivot. Recall that $k$ is the final position of the pivot after the partition.
Hence, if $j=k$ then $A[k]$ is returned and we are done. Otherwise, if $j<k$
then the $j$th element must be in $A[1..k-1]$ and the procedure is
recursively applied to that segment. If $k<j$ then the $j$th element
lies in $A[k+1..n]$, and we call |find| on that segment.

Unlike Quicksort,
where both segments of the partitioned array 
have to be sorted recursively, the \textsc{Find} algorithm
has only to work on either the left or the right segment. As 
a consequence, an iterative implementation of \textsc{Find} is almost
straightforward, and no additional auxiliary storage is needed.


\begin{algorithm}
\bigskip
\begin{pcode}
 \PROCEDURE |partition|(\tab \INOUT A : \ARRAY [1..n] \OF |integer|; l,u :|integer|; 
 \INOUT k :|integer|) \untab
 \VAR i, p :|integer|; \ENDVAR 
 \BEGIN 

    k:= l + 1; p:= A[l];
 \FOR i:= l + 1 \TO u \DO 
 \IF A[i] \LEQ p \THEN \BEGIN 
         |swap|(A[k], A[i]); 
         k:= k + 1
 \END \ENDIF \ENDFOR 
    |swap|(A[l], A[k])
 \END %
\end{pcode}
\caption{Partition of the segment $A[l:u]$}
\label{algo:partition}
\end{algorithm}

The preliminary analysis of \textsc{Find} is by Hoare~\cite{Hoare62}. In
1970, Kruseman-Aretz showed that it makes approximately $2(1+\log 2)n$
comparisons to find the median of $n$ elements~\cite{KA70}. One year after, Knuth
presented the first detailed
analysis of this algorithm~\cite{Ifip}, where he computed the
expected number of comparisons to find the $j$th out of $n$. A
similar approach may be used to compute the expected number of
\textsl{passes} or calls to |find|, the expected number of
exchanges in the array, etc. 
Devroye~\cite{Dev84} has identified upper bounds on the moments of
arbitrary order for the number of comparisons, and Mahmoud, Modarres and
Smythe~\cite{MMS95} have investigated the expectation, variance and
distribution of the number of comparisons needed to select an element
of \textsl{random rank}, that is, when $j$ is the value of a uniformly distributed
random variable, between 1 and $n$. 

Several variations of this basic scheme may yield significant
improvements in the algorithm's performance. For instance, 
instead of taking a random element as the pivot, 
a random sample of 3 elements is taken, and the middle of it
is used as the pivot element.
The idea is that it is more likely that no subfile is degenerate.
This strategy, called 
the \textsl{Median--of--three} variant,
is very well understood in the case of Quicksort~\cite{Knuth3,Sedgewick}.
Of course, the Median--of--three strategy can also be used in the context
of selection. Quite recently, Anderson and Brown~\cite{aussies}
presented a preliminary analysis of this variant of the \textsc{Find}
algorithm.

In this paper, we give a precise and detailed analysis of the
Median--of--three.  We will find an explicit expression for the
average number of passes of the recursive algorithm, when the $j$th
element has to be selected out of $n$ and for the average number of
comparisons between elements made during the partitioning.  We
show how to solve the intricate recurrences arising in the
analysis of this variant, and how the theory of hypergeometric
differential equations comes into play in the solution.

For the rest of the paper, we will assume that the $n$ given elements
are distinct. Since the behavior of the algorithm only depends on the
relative ordering of the elements and the pivot is selected from
random samples, the analysis can be carried out as if
the input were a random permutation of
$\{1,2,\dots,n\}$. In Section~\ref{sec:passes}, we present the analysis of the
expected number of passes, and in Section~\ref{sec:comparisons}, that
of the number of comparisons.

Section~\ref{sec:related-results} is devoted to discuss several related
results and various comparisons of the cost of the Median--of--three
variant with the cost of the basic algorithm. 

\section{The number of passes}
\label{sec:passes}

Let $\pgfpasses{n}{j}$ be the probability generating function of the number
of passes, when selecting the $j$th element out of $n$. The
coefficient of $z^k$ in $\pgfpasses{n}{j}$, denoted
$[z^k]\pgfpasses{n}{j}$ as usual, is by definition~\cite{GKP} 
$$[z^k]\pgfpasses{n}{j}=\Prob\{\text{``number passes to select the $j$th
out of $n$''}=k\}.$$

A file of size 1 or 2 is not treated recursively, hence
$$
\pgfpasses{1}{1}=\pgfpasses{2}{1}=\pgfpasses{2}{2}=z.
$$
For $n\ge3$ we have
\begin{equation}
\pgfpasses{n}{j} = z\, \Biggl[\
\sum_{k=1}^{j-1}\pi_{n,k}\pgfpasses{n-k}{j-k} + \pi_{n,j}
+\sum_{k=j+1}^{n}\pi_{n,k}\pgfpasses{k-1}{j}\ \Biggr]\ .
\end{equation}
Here and in the sequel, 
\begin{equation}
\pi_{n,k}=\frac{(k-1)(n-k)}{\binom n3}
\end{equation}
are the 
\textsl{splitting probabilities}. It is easy to see that this quantity
is the probability that the middle element of a random sample of 3
elements
is the $k$th element in a random permutation of $n$ elements. 
The recursion above is almost self-explanatory. If $k<j$, we
have to search in the right subfile of size $n-k$, but the sought
element is the $(j-k)$th of the subfile. 
If $k=j$, we are done, and if $k>j$ we are still 
looking for the $j$th element in the left subfile of size $k-1$.

Solving the recurrence above is a very difficult problem; however, it is
straightforward to obtain recurrences for each factorial moment
of the random variable ``number of passes'' in a systematic way, the
most important moment being the expectation. 
The average number $\passes{n}{j}$ of passes is given by $\dpgfpasses{n}{j}$. Hence
we have $\passes{1}{1}=\passes{2}{1}=\passes{2}{2}=1$ and for $n\ge3$
\begin{equation}
\passes{n}{j}=1+
\sum_{k=1}^{j-1}\pi_{n,k}\passes{n-k}{j-k}
+\sum_{k=j+1}^{n}\pi_{n,k}\passes{k-1}{j}\ .
\end{equation}
For convenience, we set $\passes{n}{j}=0$ whenever $n<j$.
We also note the symmetry $\passes{n}{j}=\passes{n}{n+1-j}$ that holds 
for obvious combinatorial reasons. 

It is now natural to
set up generating functions
$$
P_j(z)=\sum_{n\ge j}\passes{n}{j}z^n.
$$
Multiplying the recursion by $\binom n3 z^{n-3}$ and summing up we obtain
\begin{equation}
\frac16 P'''_j(z)=\frac1{(1-z)^4}-\sum_{k=3}^{j-1}\binom k3z^{k-3}
+\sum_{k=2}^{j-1}(k-1)z^{k-2}P'_{j-k}(z)+\frac{P'_j(z)}{(1-z)^2}.
\label{eq:deq1-passes}
\end{equation}
This equation holds for all $j\ge1$ and the initial values are
$P_j(0)=0$, $P'_j(z)=[j=1]$ and $P''_j(0)=2\cdot[j\le2]$, where
the value of $[R]$ is 1 if the predicate $R$ is true and 0 otherwise, 
compare~\cite{GKP}.
It is simple to reduce the order of the differential equations; we
define $Q_j(z)=P'_j(z)$ and rewrite equation~\eqref{eq:deq1-passes} as
\begin{equation}
\frac16Q''_j(z)=\frac1{(1-z)^4}-\sum_{k=3}^{j-1}\binom k3z^{k-3}
+\sum_{k=2}^{j-1}(k-1)z^{k-2}Q_{j-k}(z)+\frac{Q_j(z)}{(1-z)^2}
\label{eq:deq2-passes}
\end{equation}
with initial conditions $Q_j(0)=[j=1]$ and $Q'_j(0)=2\cdot[j\le2]$.

Solving the first few instances we get
\begin{align*}
\begin{split}
Q_1(z) & = \frac65\frac1{(1-z)^2}\log\frac1{1-z}+\frac{19}{25}
\frac1{(1-z)^2}+\frac6{25}(1-z)^3,\\
Q_2(z) & = \frac65\frac1{(1-z)^2}\log\frac1{1-z}+\frac{4}{25}
\frac1{(1-z)^2}-\frac4{25}(1-z)^3,\\
Q_3(z) & = \frac65\frac1{(1-z)^2}\log\frac1{1-z}+\frac{108}{175}
\frac1{(1-z)^2}-\frac65\log\frac1{1-z}\\ 
&\qquad\qquad\qquad\qquad
 -\frac{24}{25}+\frac6{25}(1-z)^3
+\frac{18}{175}(1-z)^5,
\end{split}
\end{align*}
etc. 

It is meaningful to define the double generating function
$$
\Q(z,u):=\sum_{j\ge1}Q_j(z)u^j.
$$
Then the system of differential equations~\eqref{eq:deq2-passes}
translates into a single
equation, viz.
\begin{equation}
\frac16\frac{\partial^2\Q}{\partial z^2}-
\left(\frac{1}{(1-z)^2}+\frac{u^2}{(1-uz)^2}\right)\Q=
\frac u{1-u}
\left(\frac{1}{(1-z)^4}-\frac{u^3}{(1-uz)^4}\right),
\label{eq:pde-passes}
\end{equation}
with the initial conditions $\Q(0,u)=u$ and $\dfrac{\partial \Q}{\partial
z}(0,u)
=2u(1+u)$.

In order to solve this equation it is helpful to express $\Q(z,u)$ as
\begin{equation}
\Q(z,u)=\frac1{(1-z)^2(1-uz)^2}\, \mathcal{E}(z,u),
\end{equation}
and substitute $z=1+t(1-u)/u$. With the notation 
\begin{equation}
\G(t,u)=\mathcal{E}\bigl(1+\frac{1-u}ut,u\bigr)
\end{equation}
the original differential equation~\eqref{eq:pde-passes} transforms into
the \textsl{hypergeometric equation}
\begin{equation}
t(1-t)\frac{\partial^2\G}{\partial t^2}
+(-4+8t)\frac{\partial\G}{\partial t}-8\G=
6(1-u)\frac{u(1-t)^4-t^4}{t(1-t)}\ ,
\label{eq:hypergeometric-de}
\end{equation}
with the initial conditions $\G\bigl(-u/(1-u),u\bigr)=u$ and 
$\dfrac{\partial\G}{\partial z}\bigl(-u/(1-u),u\bigr)=0$. 

For the reader's convenience, we recall~\cite{Kam77}
that, under certain assumptions on the parameters, 
the hypergeometric differential equation
\begin{displaymath} 
t(1-t)\, g''(t)+\bigl(c-(1+a+b)t\bigr)\, g'(t)-ab\, g(t)=0
\end{displaymath}
has in a neighbourhood of $t=0$ the solution 
\begin{displaymath} 
g(t)=c_1\cdot {}_2F_1\left(\frac[0pt]{a,b}{c}\ \bigg\vert\ t\right)+
c_2t^{1-c}\cdot {}_2F_1\left(\frac[0pt]{a-c+1,b-c+1}{2-c}\ \bigg\vert\ t\right),
\end{displaymath}
where $_2F_1$ denotes a \textsl{hypergeometric function}~\cite{GKP}. 
In our instance, the two hypergeometric functions degenerate to
polynomials (``terminating hypergeometric series''), 
and we get the homogeneous solution 
\begin{displaymath} 
\G^{\text{[hom]}}(t,u)=c_1(u)(1-2t) + c_2(u)t^5\left(1-2t+\frac{10}7t^2-\frac5{14}t^3\right).
\end{displaymath}

Using the \textsl{variation of parameters method}~\cite{Kam77}, inserting
the initial conditions, and resubstituting we find
\begin{equation}
\Q(z,u) = \QF(z,u) + u^2\QF(uz,u^{-1}) + \QS(z,u), \label{eq:D-decomp}
\end{equation}
where 
\begin{align*}
\QF(z,u) &= \frac{u}{(1-z)^2(1-uz)^2}\log\frac1{1-z}\;\Biggl\{\frac65(1-u)+
\frac{12}5u(1-z) -\frac{24}5\frac{(1+u)u^4}{(1-u)^4}(1-z)^5  \\
&\qquad
 -\frac{48}5\frac{(1+u)u^5}{(1-u)^5}(1-z)^6
 -\frac{48}7\frac{(1+u)u^6}{(1-u)^6}(1-z)^7
 -\frac{12}7\frac{(1+u)u^7}{(1-u)^7}(1-z)^8\Biggr\}, \\
\QS(z,u) &= \frac{u}{(1-z)^2(1-uz)^2}\;\Biggl\{
  -\frac{(1-u)(R(u)+94)}{175} 
  -\frac{2(uR(u)-75+124u)}{175}(1-z)  \\ 
& \qquad +\frac{u(9-5u)}{7(1-u)}(1-z)^2
  -\frac{4u^2(1+u)}{7(1-u)^2}(1-z)^3 
  +\frac{13u^3(1+u)}{7(1-u)^3}(1-z)^4 \label{eq:Dzu} \\
& \qquad +\frac{2(7S(u)+2u^4(211+379u))}{175(1-u)^4}(1-z)^5 
  +\frac{2u(2S(u)+3u^4(9+41u))}{25(1-u)^5}(1-z)^6  \\
& \qquad +\frac{4u^2(S(u)-3u^4(3-13u))}{35(1-u)^6}(1-z)^7 
 +\frac{u^3(S(u)-24u^4(1-u))}{35(1-u)^7}(1-z)^8\Biggr\}, 
\end{align*}
and $R(u):= -(1-u)(11-3u)(7-2u+u^2)$ and $S(u):=
u^5R(u)-u^4R(u^{-1})$.

We notice that the symmetry property $\passes{n}{j}=\passes{n}{n+1-j}$ is reflected
on the level of generating functions by $\Q(z,u)=u^2\Q(uz,u^{-1})$; 
in fact we have $\QS(z,u)= u^2\QS(uz,u^{-1})$. 
\medskip

Recall that $Q_j(z)=P'_j(z)$ and therefore
$\passes{n}{j}=\frac1n[z^{n-1}u^j]\Q(z,u)$. 
To extract  these coefficients from equation~\eqref{eq:D-decomp} we use
\begin{align*}
\begin{split}
&\frac1n [z^{n-1}u^r]\frac{(1-z)^i}{(1-uz)^2}\log\frac1{1-z}=\frac{r+1}{n}
\frac{(-1)^ii!}{\ffact
{(n-1-r)}{i+1}}, \quad\text{for $0\le i<n-1-r$}, \\
&\frac1n[z^{n-1}u^r]\frac{1}{(1-z)(1-uz)^2}\log\frac1{1-z}=
\frac{r+1}n H_{n-1-r}, \\
&\frac1n[z^{n-1}u^r]\frac{1}{(1-z)^2(1-uz)^2}\log\frac1{1-z}=
\frac{(r+1)(n-r)}n\left(H_{n-r} - 1\right), 
\end{split}
\end{align*}
and Theorem~\ref{theorem:avg-passes} follows. Here, and for the rest
of the paper, $\ffact{n}{i}=n(n-1)\dots(n-i+1)$ denotes the $i$th
\textsl{falling factorial} of $n$ and $H_n=\sum_{1\le i\le n}1/i$ the
$n$th harmonic number~\cite{GKP}.

\begin{theorem}
\label{theorem:avg-passes}
The average number of passes to select the $j$th element out of a
random permutation of $n$ elements using Hoare's \textsc{Find} algorithm with
Median--of--three partition is
\begin{align}
\begin{split}
\passes{n}{j} & = \frac{24}{35}H_n + \frac{18}{35}H_j+\frac{18}{35}H_{n+1-j}
+ \frac{12}{35j}+\frac{12}{35(n+1-j)} \\
& -\frac{304}{175}-\frac{6}{7n} + \frac{18j}{35n}-\frac{12(j-1)^2}{35\ffact n2}-
\frac{4(2j-3)\ffact{(j-1)}{2}}{35\ffact n3} \\
& -\frac{6(j-2)\ffact{(j-1)}{3}}{35\ffact n4}
+\frac{6(2j-5)\ffact{(j-1)}{4}}{35\ffact n5}-
\frac{4(j-3)\ffact{(j-1)}{5}}{35\ffact n6}
\end{split}
\label{eq:avg-passes}
\end{align}
for $5\le j \le n-4$. Table~1 at
the end of the paper collects also the formul{\ae} for the cases
$j=1,2,3,4$. The remaining cases, when $j\le n\le j+3$, are handled by
using the symmetry $\passes{n}{j}=\passes{n}{n+1-j}$. Since $1\le
n+1-j\le 4$ the expressions for $j=1,2,3,4$ apply.
\end{theorem}

The formula for $\passes{n}{j}$ is symmetric in $j$ and $n+1-j$, 
even though it is not apparent at the first glance. It is possible to
produce evidently symmetric expressions for $\passes{n}{j}$, but they are
messier and we stick to the presented form.


\section{The number of comparisons}
\label{sec:comparisons}

The analysis of the average number of comparisons follows the pattern
shown in Section~\ref{sec:passes}.

First, we introduce $\pgfcomp{n}{j}$, 
the probability generating function of the number of
comparisons. We will not count the comparisons made to select pivots,
i.e., to decide the middle element in the random samples of three elements.
A file of size 1 or 2 is not treated recursively, hence
$$
\pgfcomp{1}{1}=1, \quad \pgfcomp{2}{1}=\pgfcomp{2}{2}=z.
$$
For $n\ge3$ we have
\begin{equation}
\pgfcomp{n}{j}=z^{n-1}\, \Biggl[\
\sum_{k=1}^{j-1}\pi_{n,k}\pgfcomp{n-k}{j-k}+\pi_{n,j}
+\sum_{k=j+1}^{n}\pi_{n,k}\pgfcomp{k-1}{j}\ \Biggr]\ .
\end{equation}

The recurrence is obtained in the same way as the one for the number
of passes, the factor $z^{n-1}$ in front of everything counting for
the $n-1$ comparisons needed to partition the file around the pivot
element.

The average number $\comp{n}{j}$ of comparisons is given by
$\dpgfcomp{n}{j}$. 
Hence, we have $\comp{1}{1}=0$, $\comp{2}{1}=\comp{2}{2}=1$ and for $n\ge3$
\begin{equation}
\comp{n}{j}=n-1+
\sum_{k=1}^{j-1}\pi_{n,k}\comp{n-k}{j-k}
+\sum_{k=j+1}^{n}\pi_{n,k}\comp{k-1}{j}\ .
\label{eq:recurrence-comp}
\end{equation}

Again, we have $\comp{n}{j}=\comp{n}{n+1-j}$ for any $j$, $1\le j\le n$.
As in the analysis of the number of passes, 
we assume $\comp{n}{j}=0$ whenever $n<j$ and
set up generating functions
$$
C_j(z)=\sum_{n\ge j}\comp{n}{j}z^n.
$$
It turns out that the order of differential
equations for the $C_j(z)$'s, 
corresponding to the recurrence~\eqref{eq:recurrence-comp},
may be reduced by using 
$D_j(z)=C'_j(z)$ instead. As in the analysis of the number of passes, 
the bivariate generating function
$$
\D(z,u):=\sum_{j\ge1}D_j(z)u^j,
$$
satisfies a second order partial differential equation. After
appropriate transformations, the problem reduces to solving an
hypergeometric differential equation. 
We will not repeat the intermediate steps, since they are completely
analogous to those shown in the previous section. The final result is
cast into the form of Theorem~\ref{theorem:avg-cmp}. 

\begin{theorem}
\label{theorem:avg-cmp}
The average number of comparisons to select the $j$th element out of a
random permutation of $n$ elements using Hoare's \textsc{Find} algorithm with
Median--of--three partition is
\begin{align}
\begin{split}
\comp{n}{j} &= 2n+\frac{72}{35}H_n- \frac{156}{35}H_j-\frac{156}{35}H_{n+1-j} 
+\frac{36}{35j}+\frac{36}{35(n+1-j)} +\frac{113}{175}+\frac{24}{7n} +
3j \\
& -\frac{3\ffact{(j-1)}2}{n} 
-\frac{156j}{35n}-\frac{36(j-1)^2}{35\ffact n2} 
-\frac{12(2j-3)\ffact{(j-1)}{2}}{35\ffact n3} \\
& -\frac{18(j-2)\ffact{(j-1)}{3}}{35\ffact n4}
+\frac{18(2j-5)\ffact{(j-1)}{4}}{35\ffact n5}-
\frac{12(j-3)\ffact{(j-1)}{5}}{35\ffact n6}
\end{split}
\label{eq:avg-cmp}
\end{align}
for $5\le j \le n-4$. Table~2 at
the end of the paper also collects  the formul{\ae} for the cases
$j=1,2,3,4$. The remaining cases, when $j\le n\le j+3$, are handled by
using the symmetry $\comp{n}{j}=\comp{n}{n+1-j}$. Since $1\le
n+1-j\le 4$ the expressions for $j=1,2,3,4$ apply.
\end{theorem}


\section{Related results}
\label{sec:related-results}

The procedure shown in Sections~\ref{sec:passes}
and~\ref{sec:comparisons} can be used, in principle, to analyze many
other quantities such as the average number of exchanges $\exchan{n}{j}$,
the number of calls to the partition procedure ---which is not
actually the same as the number of passes---, etc.  For instance, in
the paper~\cite{aussies}, the authors make the assumption that each
partitioning phase costs $n-3$ comparisons, as opposed to the
assumption of $n-1$ comparisons to partition a file of size $n$.  The
idea behind their approach is that the comparisons between the pivot
and the other two elements in the sample during the partitioning 
can be avoided since they
were already compared when selecting the pivot.
In this instance, the result, very similar to the one given in
Theorem~\ref{theorem:avg-cmp}, is
\begin{align}
\begin{split}
\comp{n}{j} &=
 2n+\frac{24}{35}H_n- \frac{192}{35}H_j-\frac{192}{35}H_{n+1-j} 
+\frac{12}{35j}+\frac{12}{35(n+1-j)}
+\frac{921}{175}+\frac{36}{7n}
+3j \\
&-\frac{3\ffact{(j-1)}2}{n} 
-\frac{192j}{35n}-\frac{12(j-1)^2}{35\ffact n2}-
\frac{4(2j-3)\ffact{(j-1)}{2}}{35\ffact n3} \\
&-\frac{6(j-2)\ffact{(j-1)}{3}}{35\ffact n4}
+\frac{6(2j-5)\ffact{(j-1)}{4}}{35\ffact n5}-
\frac{4(j-3)\ffact{(j-1)}{5}}{35\ffact n6},
\end{split}
\end{align}
which holds for
$j\ge5$
and $n+1-j\ge5$.

Neither the previous work of Anderson and Brown~\cite{aussies} nor
this work consider the total number of comparisons, 
since the comparisons made to select the pivots were not counted. Of
course, the exact average number of comparisons $\comptot{n}{j}$ 
can be computed using
the methods presented in this paper, but it is approximately
\begin{equation*}
\comptot{n}{j} \sim \frac83\times\passes{n}{j} + \comp{n}{j},
\end{equation*}
since we need $8/3$ comparisons on the average to select the median of
three elements.
Hence, for $5\le j\le n-4$,
\begin{displaymath} 
\comptot{n}{j} = 2n+\frac{136}{35}H_n-
\frac{108}{35}H_j-
\frac{108}{35}H_{n+1-j} + \bigOh(1)
%+\frac{68}{35j}+\frac{68}{35(n+1-j)} -\frac{299}{75} \\ 
%& +\frac{8}{7n} + 3j 
%-\frac{3\ffact{(j-1)}2}{n} 
%-\frac{108j}{35n}-\frac{68(j-1)^2}{35\ffact n2} 
%-\frac{68(2j-3)\ffact{(j-1)}{2}}{105\ffact n3} \\
%& -\frac{34(j-2)\ffact{(j-1)}{3}}{35\ffact n4}
%+\frac{34(2j-5)\ffact{(j-1)}{4}}{35\ffact n5}-
%\frac{68(j-3)\ffact{(j-1)}{5}}{105\ffact n6}.
\end{displaymath}

If we assume $n-3$ comparisons to partition a
file of size $n$, instead of $n-1$, the same estimation results.


\bigskip


An interesting question that we consider now is the performance
of the algorithm when looking for the median $j=\lfloor (n+1)/2 \rfloor$
and when selecting an element at random, i.e. $j$ takes any value
between 1 and $n$ with identical probability $1/n$. We compare then these
performances with the corresponding ones for the basic algorithm; let
us recall that the average number of passes for the basic
algorithm~\cite{Ifip} is
\begin{equation}
\passes{n}{j}=H_j+H_{n+1-j}-1,
\end{equation}
whilst the average number of comparisons is 
\begin{equation}
\comp{n}{j}=
2\Big(n+3+(n+1)H_n-(j+2)H_j-(n+3-j)H_{n+1-j}\Big).\label{eq:avg-cmp-classic}
\end{equation}

If we specialize formula~\eqref{eq:avg-passes} for $n=2N+1$ and
$j=N+1$ then
\begin{align*}
\begin{split}
\passes{2N+1}{N+1} & = 
\frac{24}{35}H_{2N+1}+\frac{36}{35}H_{N+1}-\frac{4469}{2800} + {\cal
O}\left(\frac1N\right) \\
& = \frac{12}{7}\log N+\frac{12}{7}\gamma+\frac{24}{35}\log 2
-\frac{4469}{2800} +{\cal O}\left(\frac1N\right),
\end{split}
\end{align*}
On the other hand, 
the average number of passes to find the median in the classical case is
\begin{equation*}
\passes{2N+1}{N+1}=2H_{N+1}-1\sim 2\log N+ 2\gamma
-1+{\cal  O}\left(\frac1N\right).
\end{equation*}
Comparing the leading coefficients, $\frac{12}{7}$ and
$2=\frac{14}{7}$,
we see that the savings by the refined method are 14.3\%.

By taking $n=2N+1$ and
$j=N+1$ in Equations~\eqref{eq:avg-cmp}
and~\eqref{eq:avg-cmp-classic}, 
we obtain the average number of
comparisons made to search for the median, in the case of the median--of--three and
the basic algorithm, respectively. The formul{\ae} read this time
\begin{align*}
\begin{split}
\comp{2N+1}{N+1} & = 
\frac{11}2N+\frac{14893}{2800}+\frac{72}{35}H_{2N+1}-\frac{312}{35}H_{N+1}
+ {\cal O}\left(\frac1N\right) \\
& =  \frac{11}{2}N-\frac{48}{7}\log
N-\frac{48}{7}\gamma+\frac{14893}{2800}+\frac{72}{35}\log 2+{\cal
O}\left(\frac1N\right),
\end{split}
\end{align*}
and
\begin{align*}
\begin{split}
\comp{2N+1}{N+1} & = 4\Big(N + 2 + (N + 1)H_{2N+1}-(N+3)H_{N+1}\Big) \\
& =  4(1+\log 2)N-8\log N-8(\gamma-1)+4\log 2 + {\cal O}\left(\frac1N\right).
\end{split}
\end{align*}
The leading coefficients (of the order $N$), if we search for the
median, are this time $\frac{11}2=5.5$ and $4(1+\log2)=6.772588722$,
so that the savings are roughly $19\%$. To be fair, 
the total number of comparisons $\comptot{2N+1}{N+1}$ should have been used 
rather than $\comp{2N+1}{N+1}$ to compute these savings,
but it actually does not matter since
the main term in both quantities is $\frac{11}{2}N$.  


The average number of passes and comparisons
to find an element of random rank out of $n$ elements are given by 
\begin{align*}
\gpasses{n} &= \frac{1}{n}\sum_{1\le j\le n}\passes{n}{j}, \\
\gcomp{n} & = \frac{1}{n}\sum_{1\le j\le n}\comp{n}{j}. 
\end{align*}
Comparing the values of $\gpasses{n}$ for the classical and the
median--of--three algorithms, we find that they are
$2H_n+ \bigOh(1)$ and $\frac{12}{7}H_n+\bigOh(1)$ respectively, and
hence the average savings are $14.3\%$.
On the other hand, $\gcomp{n}=3n-8H_n+\bigOh(1)$ for the standard algorithm and 
$\gcomp{n}=\frac{5}{2}n-\frac{48}{7}H_n+\bigOh(1)$ for the variant, showing that
an average of $16.6\%$ of the comparisons are saved when using the
median--of--three\footnote{As in the example where we considered the number
of comparisons to find the median, the main term in $\gcomp{n}$ does
not change if we use $\comptot{n}{j}$ instead of $\comp{n}{j}$ to
compute this ``grand'' average.}.

\begin{ackno}
We thank Friedrich Hubalek for valuable discussions.
The computer algebra system \textsc{Maple} was heavily used in the
preparation
of this work.
\end{ackno}

\bibliographystyle{plain}

\begin{thebibliography}{10}

\bibitem{aussies}
D.~H. Anderson and R.~Brown.
\newblock Combinatorial aspects of {C.\;A.\;R.\;Hoare's} {F}ind algorithm.
\newblock {\em Australasian Journal of Combinatorics}, 5:109--119, 1992.

\bibitem{BFPRT70}
M.~Blum, R.W. Floyd, V.R. Pratt, R.~Rivest, and R.~Tarjan.
\newblock Time bounds for selection.
\newblock {\em J. Computer and System Sciences}, 7:448--461, 1973.

\bibitem{Dev84}
L.~Devroye.
\newblock Exponential bounds for the running time of a selection algorithm.
\newblock {\em J. Computer and System Sciences}, 29:1--7, 1984.

\bibitem{handbook2}
G.H. Gonnet and R.~{Baeza-Yates}.
\newblock {\em Handbook of {A}lgorithms and {D}ata {S}tructures - In {P}ascal
  and {C}}.
\newblock Addison-Wesley, Reading, MA, 2nd edition, 1991.

\bibitem{GKP}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik.
\newblock {\em Concrete {M}athematics}.
\newblock Addison-Wesley, Reading, MA, 1989.

\bibitem{Hoare61}
C.~A.~R. Hoare.
\newblock Find ({A}lgorithm 65).
\newblock {\em Communications of the ACM}, 4:321--322, 1961.

\bibitem{Hoare62}
C.~A.~R. Hoare.
\newblock Quicksort.
\newblock {\em Computer Journal}, 5:10--15, 1962.

\bibitem{Kam77}
E.~Kamke.
\newblock {\em Differentialgleichungen: L\"osungsmethoden und {L}\"osungen}.
\newblock Teubner, Stuttgart, 1977.

\bibitem{Ifip}
D.~E. Knuth.
\newblock Mathematical analysis of algorithms.
\newblock In {\em Information Processing '71, Proc. of the 1971 IFIP Congress},
  pages 19--27, Amsterdam, 1972. North-Holland.

\bibitem{Knuth3}
D.~E. Knuth.
\newblock {\em The {A}rt of {C}omputer {P}rogramming: {S}orting and
  {S}earching}, volume~3.
\newblock Addison-Wesley, Reading, MA, 1973.

\bibitem{MMS95}
H.M. Mahmoud, R.M. Modarres, and R.T. Smythe.
\newblock Analysis of one-sided quicksort: An algorithm for order statistics.
\newblock {\em RAIRO, Theoretical Informatics and Applications}, 29:255--276,
  1995.

\bibitem{Sedgewick}
R.~Sedgewick.
\newblock {\em Quicksort}.
\newblock Garland, New York, 1978.

\bibitem{KA70}
M.H. van Emden.
\newblock Increasing the efficiency of quicksort.
\newblock {\em Communications of the ACM}, 13:563--567, 1970.

\end{thebibliography}


\addtolength{\tabcolsep}{2ex}
\renewcommand{\arraystretch}{3}

\begin{table}
\begin{center}
\begin{tabular}{|c|l|}\hline 
$j$ & $\hfil \passes{n}{j}$ \\\hline\hline
1 & $\displaystyle\frac65H_n-\frac{11}{25},\qquad\mbox{for $n\ge5$}$ \\[2mm]\cline{2-2}
  & $\displaystyle \passes{1}{1}=1,\ \passes{2}{1}=1,\ \passes{3}{1}=2,\ \passes{4}{1}=2$ \\[2mm]\hline
2 & $\displaystyle\frac65H_n-\frac{26}{25},\qquad\mbox{for $n\ge5$}$ \\[2mm]\cline{2-2}
  & $\displaystyle \passes{2}{2}=1, \ \passes{3}{2}=1,\ \passes{4}{2}=\frac32$ \\[2mm]\hline
3 & $\displaystyle\frac65H_n-\frac{102}{175}-\frac65\frac1{\ffact
n2},\qquad\mbox{for $n\ge7$}$ \\[2mm]\cline{2-2}  
  & $\displaystyle \passes{3}{3}=2, \ \passes{4}{3}=\frac32,\ \passes{5}{3}=\frac{11}{5}, 
   \  \passes{6}{3}=\frac{23}{10}$ \\[2mm]\hline
4 & $\displaystyle \frac65H_n-\frac{209}{350}-\frac{18}5\frac1{\ffact
n2}-\frac{12}5\frac1{\ffact n3},\qquad\mbox{for $n\ge8$}$ \\[2mm]\cline{2-2}
  & $\displaystyle \passes{4}{4}=2,\ \passes{5}{4}=\frac{17}{10}, \ \passes{6}{4}=\frac{23}{10},
\ \passes{7}{4}=\frac{12}{5}$ \\[2mm]\hline
$5\le j\le n-4$ & $
\begin{array}{l}
\displaystyle \frac{24}{35}H_n+ \frac{18}{35}H_j+\frac{18}{35}H_{n+1-j} \\
\displaystyle +\frac{12}{35j}+\frac{12}{35(n+1-j)} -\frac{304}{175}-\frac{6}{7n} \\
\displaystyle +\frac{18j}{35n}-\frac{12(j-1)^2}{35\ffact n2}-
\frac{4(2j-3)\ffact{(j-1)}{2}}{35\ffact n3} \\
\displaystyle -\frac{6(j-2)\ffact{(j-1)}{3}}{35\ffact n4}
+\frac{6(2j-5)\ffact{(j-1)}{4}}{35\ffact n5}-
\frac{4(j-3)\ffact{(j-1)}{5}}{35\ffact n6}
\end{array}
$
\\[-1cm]
\mbox{} & \mbox{} \\
\hline
\end{tabular}
\end{center} 

\bigskip

\caption{Average number of passes to select the $j$th element out
of $n$ (Theorem~\ref{theorem:avg-passes}).}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{|c|l|}\hline 
$j$ & $\hfil \comp{n}{j}$ \\\hline\hline
1 & $\displaystyle 2n-\frac{12}5H_n+\frac{12}{25},\qquad\mbox{for $n\ge5$}$ \\[2mm]\cline{2-2}
  & $\displaystyle \comp{1}{1}=0,\  \comp{2}{1}=1, \ \comp{3}{1}=2,\ \comp{4}{1}=\frac72$ \\[2mm]\hline
2 & $\displaystyle 2n-\frac{12}5H_n+\frac{12}{25},\qquad\mbox{for $n\ge5$}$ \\[2mm]\cline{2-2}
  & $\displaystyle \comp{2}{2}=1,\ \comp{3}{2}=2, \ \comp{4}{2}=\frac72$ \\[2mm]\hline
3 & $\displaystyle 2n-\frac{12}5H_n+\frac{314}{175}-\frac6n+\frac{12}{5\ffact n2},\qquad\mbox{for $n\ge7$}$ \\[2mm]\cline{2-2}  
  & $\displaystyle \comp{3}{3}=2, \ \comp{4}{3}=\frac72, \ \comp{5}{3}=\frac{26}{5}, 
     \ \comp{6}{3}=7$ \\[2mm]\hline
4 & $\displaystyle
2n-\frac{12}5H_n+\frac{634}{175}-\frac{18}n+\frac{36}{5\ffact
n2}+\frac{24}{5\ffact n3},\qquad\mbox{for $n\ge8$}$ \\[2mm]\cline{2-2}
  & $\displaystyle \comp{4}{4}=\frac72, \ \comp{5}{4}=5,\ \comp{6}{4}=7,
\ \comp{7}{4}=\frac{316}{35}$ \\[2mm]\hline
$5\le j\le n-4$ & $
\begin{array}{l}
\displaystyle 2n+\frac{72}{35}H_n- \frac{156}{35}H_j-\frac{156}{35}H_{n+1-j} \\
\displaystyle +\frac{36}{35j}+\frac{36}{35(n+1-j)}
+\frac{113}{175}+\frac{24}{7n}
+3j-\frac{3\ffact{(j-1)}2}{n} \\
\displaystyle -\frac{156j}{35n}-\frac{36(j-1)^2}{35\ffact n2}-
\frac{12(2j-3)\ffact{(j-1)}{2}}{35\ffact n3} \\
\displaystyle -\frac{18(j-2)\ffact{(j-1)}{3}}{35\ffact n4}
+\frac{18(2j-5)\ffact{(j-1)}{4}}{35\ffact n5}-
\frac{12(j-3)\ffact{(j-1)}{5}}{35\ffact n6}
\end{array}
$
\\[-1cm]
\mbox{} & \mbox{} \\
\hline
\end{tabular}
\end{center} 

\bigskip

\caption{Average number of comparisons to select the $j$th element out
of $n$ (Theorem~\ref{theorem:avg-cmp}).}
\end{table}

\end{document}


