Selection Algorithms with Small Groups
We revisit the selection problem, namely that of computing the $i$th order statistic of $n$ given elements, in particular the classic deterministic algorithm by grouping and partition due to Blum, Floyd, Pratt, Rivest, and Tarjan (1973). Whereas the original algorithm uses groups of odd size at least $5$ and runs in linear time, it has been perpetuated in the literature that using smaller group sizes will force the worst-case running time to become superlinear, namely $\Omega(n \log{n})$. We first point out that the usual arguments found in the literature justifying the superlinear worst-case running time fall short of proving this claim. We further prove that it is possible to use group size smaller than $5$ while maintaining the worst case linear running time. To this end we introduce three simple variants of the classic algorithm, the repeated step algorithm, the shifting target algorithm, and the hyperpair algorithm, all running in linear time.
\section{Introduction} \label{sec:intro}

Together with sorting, selection is one of the most widely used
procedure in computer algorithms. Indeed, it is easy to find hundreds
if not thousands of algorithms  (documented in at least as many
research articles) that use selection as a subroutine. A classical
example is~\cite{Me85}. 

Given a sequence $A$ of $n$ numbers (usually stored in an array), 
and an integer (target) parameter $1\leq i\leq n$, 
the selection problem asks to find the $i$th smallest element in $A$. 
Trivially sorting solves the selection problem, but if one aims at a
linear time algorithm, a higher level of sophistication is needed.  
A now classical approach for selection~\cite{BFP+73,FR75,Hy76,SPP76,Y76} 
from the 1970s is to use an element in $A$ as a pivot to partition $A$
into two smaller subsequences and recurse on one of them 
with a (possibly different) selection parameter $i$.  

The time complexity of this kind of algorithms is sensitive to the
pivots used. For example, if a good pivot is used, many elements in
$A$ can be discarded; while if a bad pivot is used, in the worst case,
the size of the problem may be only reduced by a constant, leading to a
quadratic worst-case running time. But choosing a good pivot can be
time consuming.  

Randomly choosing the pivots yields a well-known randomized algorithm
with expected linear running time
(see {e.g.},~\cite[Ch.~9.2]{CLR+09},~\cite[Ch.~13.5]{KT06}, or~\cite[Ch.~3.4]{MU05}),
however its worst case running time is quadratic in $n$. 

The first deterministic linear time selection algorithm \textsc{select }
(called \textsc{pick} by the authors), in fact a theoretical
breakthrough at the time, was introduced by Blum~{et~al.}~\cite{BFP+73}.
By using the median of medians of small (constant size) disjoint groups of $A$, 
good pivots that guarantee reducing the size of the problem by a
constant fraction can be chosen with low costs. 
The authors~\cite[page~451, proof of Theorem~1]{BFP+73} required 
the group size to be at least $5$ for the \textsc{select } algorithm to
run in linear time. It has been largely perpetuated in the literature
the idea that \textsc{select } with groups of $3$ or $4$ does not run in linear time. 
Even an exercise of the book by Cormen~{et~al.}~\cite[page~223,
  exercise~{9.3-1}]{CLR+09} asks the readers to argue that 
``\textsc{select } does not run in linear time if groups of $3$ are used''.

We first point out that the argument used in the solution to this
exercise~\cite[page~23]{CLL09} is invalid failing to provide an input
sequence with one third of the elements being discarded in each
recursive call in both the current sequence and its sequence of medians;
the difficulty (and the flaw in the argument) lies in the fact that
these two sequences are not disjoint thus cannot be constructed 
or controlled independently. 
The question whether the original \textsc{select } algorithm runs in linear time
with groups of $3$ remains open at the time of this writing. 

Further, we show that this restriction on the group size is
unnecessary, namely that group sizes 3 or 4 can be used to 
obtain a deterministic linear time algorithm for the selection problem. 
Since selecting the median in smaller groups is easier to implement
and requires fewer comparisons ({e.g.}, $3$ comparisons for group size
$3$ versus $6$ comparisons for group size $5$), 
it is attractive to have linear time selection algorithms that use
smaller groups. Our main result concerning selection with small
group size is summarized in the following theorem.  
\begin{theorem} \label{thm:thm1}
There exist suitable variants of \textsc{select } with groups of $3$ and $4$ 
running in $O(n)$ time.
\end{theorem}


\paragraph{Historical background.}
The interest in selection algorithms
has remained high over the years with many exciting
developments ({e.g.}, lower bounds, parallel algorithms, etc) taking
place; we only cite a few
here~\cite{AKSS89,BJ85,CM89,DHU+01,DZ96,DZ99,FR75,FG79,Ho61,J88,Ki81,Pa96,YY82,Y76}. 
We also refer the reader to the dedicated book chapters on selection
in~\cite{AHU83,Ba88,CLR+09,DPV08,KT06,Kn98} and the recent article~\cite{Ki13}.


\paragraph{Outline.}
In Section~\ref{sec:prelim}, the classical \textsc{select } algorithm is 
introduced (rephrased) under standard simplifying assumptions. 
In Section~\ref{sec:repeat}, we introduce a variant of \textsc{select}, 
the \emph{repeated step} algorithm, which runs in linear time with
both group size $3$ and $4$.  
With groups of $3$, the algorithm executes a certain step, 
``group by $3$ and find the medians of the groups'', twice in a row.   
In Section~\ref{sec:shift}, we introduce another variant of \textsc{select}, 
the \emph{shifting target} algorithm, 
a linear time selection algorithm with group size~$4$. 
In each iteration, upper or lower medians are used based on the
current rank of the target, and the shift in the target parameter $i$ is
controlled over three consecutive iterations. 
In Section~\ref{sec:remark}, we conclude with some remarks and 
a conjecture on the running time of the original \textsc{select } algorithm
from~\cite{BFP+73} with groups of $3$ and~$4$.  


\section{Preliminaries} \label{sec:prelim}

Without affecting the results, the following two standard
simplifying assumptions are convenient:
(i)~the input sequence $A$ contains $n$ distinct numbers; and 
(ii)~the floor and ceiling functions are omitted in the descriptions of
the algorithms and their analyses.
Under these assumptions, \textsc{select } with groups of $5$ (from~\cite{BFP+73}) can
be described as follows (using this group size has become increasingly
popular, see {e.g.},~\cite[Ch.~9.2]{CLR+09}): 
\begin{enumerate} \itemsep 2pt
\item \label{alg5:step1}
If $n\leq 5$, sort $A$ and return the $i$th smallest number.
\item
Arrange $A$ into groups of size 5.
Let $M$ be the sequence of medians of these $n/5$ groups.
Select the median of $M$ recursively, let it be $m$.
\item
Partition $A$ into two subsequences $A_1=\{x|x<m\}$ and $A_2=\{x|x>m\}$
(order of other elements is preserved).
If $|A_1|=i-1$, return $m$. 
Otherwise if $|A_1|>i-1$, go to step~\ref{alg5:step1} with
$A \leftarrow A_1$ and $n\leftarrow |A_1|$. 
Otherwise go to step~\ref{alg5:step1} with $A \leftarrow A_2$, $n\leftarrow |A_2|$ and
$i\leftarrow i-|A_1|-1$.
\end{enumerate}

Denote the worst case running time 
of the recursive selection algorithm on an $n$-element input by $T(n)$.
As shown in Figure~\ref{fig:group5}, at least $(n/5)/2*3=3n/10$
elements are discarded at each iteration, which yields the recurrence
$$T(n)\leq T(n/5)+T(7n/10)+O(n).$$
Since the coefficients sum to $1/5+7/10=9/10<1$, the
recursion solves to $T(n)=\Theta(n)$ (as it is well-known). 

\medskip
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.6]{group5.pdf}
\vspace*{0.05in}
\caption{One iteration of the \textsc{select } algorithm with group size 5.
At least $3n/10$ elements can be discarded.}
\label{fig:group5}
\end{figure}


\section{The Repeated Step Algorithm} \label{sec:repeat}

Using group size $3$ directly in the \textsc{select } algorithm in \cite{BFP+73} yields
\begin{equation} \label{eq:4}
T(n)\leq T(n/3)+T(2n/3)+O(n), 
\end{equation}
which solves to $T(n)=O(n\log n)$.
Here a large portion (at least one third) of $A$ is discarded in each iteration 
but the cost of finding such a good pivot is too high, namely $T(n/3)$.
The idea of our \emph{repeated step} algorithm, inspired by the
algorithm in~\cite{BCC+00}, is to find a weaker
pivot in a faster manner by performing the operation 
``group by $3$ and find the medians'' twice in a row  
(as illustrated in Figure~\ref{fig:group3}).

\paragraph{Algorithm}
\begin{enumerate} \itemsep 2pt
\item
\label{alg3:step1}
If $n\leq 3$, sort $A$ and return the $i$t smallest number.
\item
\label{alg3:step2}
Arrange $A$ into groups of size $3$.
Let $M$ be the sequence of medians of these $n/3$ groups.
\item
Arrange $M$ into groups of size $3$.
Let $M'$ be the sequence of medians of these $n/9$ groups.
\item \label{alg3:step3}
Select the median of $M'$ recursively, let it be $m$.
\item
Partition $A$ into two subsequences $A_1=\{x|x<m\}$ and $A_2=\{x|x>m\}$.
If $|A_1|=i-1$, return $m$. 
Otherwise if $|A_1|>i-1$, go to step~\ref{alg3:step1} with
$A\leftarrow A_1$ and $n\leftarrow |A_1|$. 
Otherwise go to step~\ref{alg3:step1} with $A\leftarrow A_2$, $n\leftarrow |A_2|$ and
$i\leftarrow i-|A_1|-1$.
\end{enumerate}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.6]{group3.pdf}
\caption{One iteration of the \emph{repeated step} algorithm with groups of $3$. 
Empty disks represent elements that are guaranteed to be smaller or equal to $m$.}
\label{fig:group3}
\end{figure}

\paragraph{Analysis.}
Since elements are discarded if and only if they are too large or too
small to be the $i$th smallest element, the correctness of the algorithm follows.
Regarding the time complexity of this algorithm, we have the following lemma:
\begin{lemma} \label{lem:1}
The repeated step algorithm with groups of $3$ runs in $\Theta(n)$
time on an $n$-element input. 
\end{lemma}
\begin{proof}
By finding the median of medians of medians instead of the median of medians, 
the cost of selecting the pivot $m$ reduces from $T(n/3)+O(n)$ to $T(n/9)+O(n)$.
We need to determine how well $m$ partitions $A$ in the worst case.
In step~\ref{alg3:step3}, $m$ is guaranteed to be greater or equal to
$(n/9)/2*2=n/9$ elements in $M$. 
Each element in $M$ is a median of a group of size $3$ in $A$, so it is
greater or equal to 2 elements in its group. 
All the groups of $A$ are disjoint, thus $m$ is at least greater or
equal to $2n/9$ elements in $A$. 
Similarly, $m$ is at least smaller or equal to $2n/9$ elements in $A$.
Thus, in the last step, at least $2n/9$ elements can be discarded.
The recursive call in step~\ref{alg3:step3} takes $T(n/9)$ time.
So the resulting recurrence is
$$T(n)\leq T(n/9)+T(7n/9)+O(n),$$ 
and since the coefficients on the right side sum to $8/9<1$, 
we have $T(n)=\Theta(n)$, as required.
\end{proof}


\section{The Shifting Target Algorithm} \label{sec:shift}

In the \textsc{select } algorithm introduced in \cite{BFP+73}, the group size
is restricted to odd numbers in order to avoid the calculation of the
average of the upper and lower median. 
For group size of $4$, depending on the choice of upper, lower or average median, 
there are three possible partial orders to be considered (see Figure~\ref{fig:partial}). 
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.6]{partialOrder.pdf}
\caption{Three partial orders of $4$ elements based on the upper (left),
  lower (middle) and average (right) medians. 
The empty square represents the average of the upper and lower
median which is not necessarily part of the $4$-element sequence.} 
\label{fig:partial}
\end{figure}

If the upper (or lower) median is always used, only $(n/4)/2*2=n/4$
elements are guaranteed  
to be discarded in each iteration (see Figure~\ref{fig:group4_lower})
which gives the recurrence 
\begin{equation} \label{eq:1}
T(n)\leq T(n/4)+T(3n/4)+O(n).
\end{equation}
The term $T(n/4)$ is for the recursive call to find the median of all $n/4$ medians.
This recursion solves to $T(n)=O(n\log n)$.
Even if we use the average of the two medians, the recursion remains the same
since only $2$ elements from each of the $(n/4)/2=n/8$ groups are
guaranteed to be discarded. 

Observe that if the target parameter satisfies $i \leq n/2$ (resp., $i \geq n/2$),
using the lower (resp., upper) median gives a better chance to discard
more elements and thus obtain a better recurrence; 
detailed calculations are given in the proof of Lemma~\ref{lem:2}. 
Inspired by this idea, we propose the \emph{shifting target} algorithm
as follows:
\paragraph{Algorithm}
\begin{enumerate} \itemsep 2pt
\item
\label{alg4:step1}
If $n\leq 4$, sort $A$ and return the $i$th smallest number.
\item
Arrange $A$ into groups of size $4$.
Let $M$ be the sequence of medians of these $n/4$ groups.
If $i\leq n/2$, the lower medians are used; otherwise the upper medians are used.
Select the median of $M$ recursively, let it be $m$.
\item
Partition $A$ into two subsequences $A_1=\{x|x<m\}$ and $A_2=\{x|x>m\}$.
If $|A_1|=i-1$, return $m$. 
Otherwise if $|A_1|>i-1$, go to step~\ref{alg4:step1} with
$A\leftarrow A_1$ and $n\leftarrow |A_1|$. 
Otherwise go to step~\ref{alg4:step1} with $A\leftarrow A_2$, $n\leftarrow |A_2|$ and
$i\leftarrow i-|A_1|-1$.
\end{enumerate}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.6]{group4.pdf}
\caption{Group size $4$ with lower medians used.}
\label{fig:group4_lower}
\end{figure}

\paragraph{Analysis.}
Regarding the time complexity, we have the following lemma:
\begin{lemma} \label{lem:2}
The shifting target algorithm with group size $4$ runs in $\Theta(n)$
time on an $n$-element input. 
\end{lemma}
\begin{proof}
Assume first that $i\leq n/4$ in some iteration so the lower
medians are used. Recall that $m$ is guaranteed to be greater or equal
to $(n/4)/2*2=n/4$ numbers in $A$. 
So either $m$ is the $i$th smallest element in $A$ 
or at least $(n/4)/2*3=3n/8$ largest numbers are discarded (see
Figure~\ref{fig:group4_lower}), hence the worst-case running time
recurrence is
\begin{equation} \label{eq:2}
T(n)\leq T(n/4)+T(5n/8)+O(n).
\end{equation} 
Observe that in this case the coefficients on the right side sum to
$7/8<1$, yielding a linear solution, as required.

Now consider the case $n/4<i\leq n/2$, so the lower medians are used.
If $|A_1| \geq i$, {i.e.}, the rank of $m$ is higher than $i$, again at least
$(n/4)/2*3=3n/8$ largest numbers are discarded and~\eqref{eq:2} applies.
Otherwise, suppose that only $t =|A_1| \geq (n/4)/2*2=n/4$ smallest
numbers are discarded. Then in the next iteration, $i'=i-t$, $n'=n-t$.

If $i'\leq n'/4$, at least $3n'/8$ numbers are discarded.
The first iteration satisfies recurrence~\eqref{eq:1} and we 
can use recurrence~\eqref{eq:2} to bound the term $T(3n/4)$ from above.
We deduce that in two iterations the worst case running time satisfies the recurrence: 
\begin{align} \label{eq:3}
T(n)&\leq T(n/4)+T(3n/4)+O(n) \nonumber \\
&\leq T(n/4)+ T((3n/4)/4) + T((3n/4)*5/8) + O(n)  \nonumber \\
&= T(n/4)+T(3n/16)+T(15n/32)+O(n).
\end{align}
Observe that the coefficients on the right side sum to $29/32<1$, yielding
a linear solution, as required. Subsequently, we can therefore assume
that $i' \geq n'/4$. We have
\begin{align*}
i'/n'&=(i-t)/(n-t)\\
&\leq(i-n/4)/(n-n/4)\\
&\leq(n/2-n/4)/(n-n/4)\\
&=1/3.
\end{align*}
Since $1/4<i'/n'\leq 1/3 \leq 1/2$, the lower medians will be used.
As described above, if at least $3n'/8$ largest numbers are discarded, in two iterations,
the worst case running time satisfies the same recurrence~\eqref{eq:3}.

So suppose that only $t'\geq (n'/4)/2*2=n'/4$ smallest numbers are discarded.
Let $i''=i'-t'$, $n''=n'-t'$. We have
\begin{align*}
i''/n''&=(i'-t')/(n'-t')\\
&\leq(i'-n'/4)/(n'-n'/4)\\
&\leq(n'/3-n'/4)/(n'-n'/4)\\
&=1/9.
\end{align*}
Since $i''/n''<1/4$, in the next iteration, at least $3n''/8$ numbers will
be discarded. The first two iterations satisfy recurrence~\eqref{eq:1} and we 
can use recurrence~\eqref{eq:2} to bound the term $T(9n/16)$ from above.
We deduce that in three iterations the worst case running time satisfies the recurrence: 
\begin{align*}
T(n)&\leq T(n/4)+T(3n/4)+O(n)\\
&\leq T(n/4)+ T((3n/4)/4) + T((3n/4)*3/4) + O(n)\\
&= T(n/4)+T(3n/16)+T(9n/16)+O(n)\\
&\leq T(n/4)+T(3n/16)+ T((9n/16)/4) + T((9n/16)*5/8) + O(n)\\
&= T(n/4)+T(3n/16)+T(9n/64)+T(45n/128)+O(n).
\end{align*}
The sum of the coefficients on the right side is $119/128<1$, so again
the solution is $T(n)=\Theta(n)$.

By symmetry, the analysis also holds for the case $i \geq n/2$, and the
proof of Lemma~\ref{lem:2} is complete. 
\end{proof}


\section{Concluding Remarks}\label{sec:remark}

A similar idea of repeating the group step also applies to the case of
groups of $4$ and yields 
$$T(n)\leq T(n/16)+T(7n/8)+O(n),$$ 
which gives another
linear time selection algorithm with group size $4$. 

Another variant of \textsc{select } with group size $4$ can be obtained by using the ideas 
of both algorithms together, {i.e.}, repeat the grouping by $4$ step twice
in a row while $M$ contains the lower medians and $M'$ contains the
upper medians (or vice versa). 
Recursively selecting the median $m$ of $M'$ takes time $T(n/16)$.
Notice that $m$ is greater or equal to at least $(n/16)/2*3=3n/32$ elements in $M$ 
of which each is greater or equal to 2 elements in its group in $A$.
So $m$ is greater or equal to at least $3n/16$ elements of $A$.
Also, $m$ is smaller or equal to at least $(n/16)/2*2=n/16$ elements in $M$
of which each is smaller or equal to $3$ elements in its group of $A$.
So $m$ is smaller or equal to at least $3n/16$ elements of $A$, thus
the resulting recurrence is 
$$T(n)\leq T(n/16)+T(13n/16)+O(n), $$
again with a linear solution, as desired. 


\paragraph{Final comment.} 
The question whether the original selection algorithm introduced
in~\cite{BFP+73} (outlined in Section~\ref{sec:prelim}) 
runs in linear time with group size 3 and $4$ remains open.
Although the recurrences 
 %
\begin{align*}
T(n)&\leq T(n/3)+T(2n/3)+O(n)\text{, and}\\
T(n)&\leq T(n/4)+T(3n/4)+O(n)
\end{align*}
(see~\eqref{eq:4} and~\eqref{eq:1}) for its worst-case running time
with these group sizes both solve to $T(n)=O(n\log n)$,  
we believe that they only give non-tight upper bounds on the worst case scenarios.
In any case, and against popular belief we think that $\Theta(n \log{n})$ is
\emph{not} the answer:
\begin{conjecture}
The \textsc{select } algorithm introduced by Blum~{et~al.}~\cite{BFP+73} 
runs in $o(n \log{n})$
time with groups of $3$ or $4$. 
\end{conjecture}





2014-09-15T02:01:28.000
1409
1409.3600
en
https://arxiv.org/abs/1409.3600
We revisit the selection problem, namely that of computing the $i$th order statistic of $n$ given elements, in particular the classic deterministic algorithm by grouping and partition due to Blum, Floyd, Pratt, Rivest, and Tarjan (1973). Whereas the original algorithm uses groups of odd size at least $5$ and runs in linear time, it has been perpetuated in the literature that using smaller group sizes will force the worst-case running time to become superlinear, namely $\Omega(n \log{n})$. We first point out that the usual arguments found in the literature justifying the superlinear worst-case running time fall short of proving this claim. We further prove that it is possible to use group size smaller than $5$ while maintaining the worst case linear running time. To this end we introduce three simple variants of the classic algorithm, the repeated step algorithm, the shifting target algorithm, and the hyperpair algorithm, all running in linear time.
Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
Selection Algorithms with Small Groups
Qwen/Qwen-72B
1. YES
2. YES