# Faster selection algorithm for small order statistics

SELECT(A,p,r,i) is an algorithm that

1. partitions $$A[p:r]$$ around the $$i$$ th order statistic ie. in the output, we have $$l\in A[p:p+i-2]. Where $$A[p+i-1]$$ is the $$i\in \{1,...,r-p+1\}$$ order statistic (basically the $$i$$ th smallest element).

2. returns the $$i$$ th order statistic

3. worst case run time is $$\Theta(n)$$

it's same as the popular RANDOMIZED-SELECT e.g. the std::nth_element in C++ (I guess) except the run time and implementation.

The problem is that

Denote by $$S(n)$$ the worst case number of comparisons used by SELECT to select the $$i$$ the order statistic from $$n$$ numbers . When $$i$$ is small relative to $$n$$, below algorithm makes fewer comparisons in worst case.

Describe an algorithm that uses $$U_i(n)$$ comparisons to find the $$i$$ th smallest of $$n$$ elements, where $$\newcommand{\floor}[1]{\lfloor #1\rfloor} \newcommand{\ceil}[1]{\lceil #1\rceil} U_i(n) = \left\{\begin{array}{cc} S(n)&\text{if } i\ge n/2 \\ \floor{n/2}+U_i(\ceil{n/2})+S(2i)& \text{otherwise } \end{array}\right.$$ Hint: Begin with $$\lfloor n/2\rfloor$$ disjoint pairwise comparisons, and recurse on the set containing the smaller element from each pair. [1]

But I still have no idea, because there's no guarantee that the set $$Q$$ containing the smaller element from each pair contains the $$i$$ th smallest element e.g. suppose we want $$2$$ nd smallest in $$2,1,3,4,6,5$$, then one possible $$Q$$ is $$\{1,3,5\}$$ which doesn't contain the $$2$$ nd smallest ie. $$2$$.

I'm even more confused by the extra $$S(2i)$$ term, like which $$2i$$ elements are we going to run SELECT on ?

[1] Introduction to Algorithms,MIT

• Hint: Assume for simplicity that $n$ is even, and let the pairs be $(x_j,y_j)$ where $x_j < y_j$ and $x_1 < \cdots < x_{n/2}$. Then the $i$'th smallest element of the entire array is also the $i$'th smallest element in $(x_1,y_1),\dots,(x_i,y_i)$. (You need to strengthen the algorithm so that it returns the $i$ smallest elements.) Commented Aug 11, 2023 at 15:04

Thanks to comment by @Yuval Filmus I get the idea. Basically we abuse transitivity that $$x_j< x_{j+1}$$ and $$x_{j+1}< y_{j+1}\implies x_j< y_{j+1}$$. Therefore we can conclude $$(x_j,y_j)$$ can never be one of $$i$$ smallest for any $$i by partitioning the array around $$(x_i,y_i)$$ using SELECT (we select only on $$x$$ entries but we move pairs around, not elements).

As we go deeper into recursion, entries e.g. $$x_j$$ will be become pair of pairs of ... below program resolves this by using a doubly link list, where we always ensure $$list.front()$$ is the smallest element in the whole list. We don't care about the relative ordering of other elements in the list however.

Below program consists of few stages, for the base case we just run SELECT (or nth_element which is similar). For recursive case, we have

• pairing stage: form $$(x_j,y_j)$$ such that $$x_j and put them at front of array $$A[0:n/2-1]$$. The rest of the array $$A[n/2-1:n-1]$$ is empty due to pairing.

• recursion stage: recurse on $$n/2$$. Select the $$i$$ smallest $$(x_j,y_j)$$ pairs (in terms of $$x$$ entry) and put them at the front of array $$A[0:i-1]$$. So that $$x_h\in A[0:i-1].

• unpairing stage: we know pairs in $$A[i:n/2-1]$$ can never contain any of $$i$$ smallest elements in $$A$$, so we push them to the back and unpair them (get out of the way). $$A[0:i-1]$$ surely contains all $$i$$ smallest elements (but we don't know where exactly) so we unpair them near the front of array $$A[0:2i-1]$$ first.

• selection stage: (this's the actual work) select the $$i$$ smallest elements in $$A[0:2i-1]$$ and put them at the front of array $$A[0:i-1]$$. Then returns to caller (which will then unpair what it has paired...).

Below is an implementation which selects in place. Although we're frequently moving large lists around, it's actually quite fast thanks to move semantics in C++. The slower part is probably the link list traversal during unpairing.

input: 9 12 7 5 -1 19 3 2 45 18 33 6 -35 98 111 160
3 smallest: -35 -1 2

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;

//assume n is powers of 2. if not we may break n into powers of 2 and combine solutions.
//A is input array, initially A[i] is a list containing only 1 element of type T
//i is the order statistic we desire, takes value in 1,...,n
//selects in place so that A[0:i-1] contains i smallest elements upon return
//to answer the question simply replace nth_element with SELECT
template<typename T>
void SMALL_ORDER_STAT_SELECT(vector<list<T> >&A,int n,int i){
if(i>=n/2)
//partition subarray A[0:n-1] around the ith order statistic
nth_element(A.begin(),A.begin()+i-1,A.begin()+n,[](list<T>&a,list<T>&b){return a.front()<b.front();});
else{
//pairing step
for(int j=0;j<n/2;++j){
//so that A[j].front is smallest in A[j]. But we don't know relative order within A[j] other than that.
if(A[j].front()<A[n/2+j].front())
A[j].splice(A[j].end(),A[n/2+j]);//pair
else
A[j].splice(A[j].begin(),A[n/2+j]);//pair
}
SMALL_ORDER_STAT_SELECT(A,n/2,i);//so that A[0:i-1] contains pairs each with one of the i smallest fronts
//unpairing step
//move indices [i,n/2) to [2i,i+n/2)
//we know those entries cannot contain the ith smallest elements (they arn't important)
//so push them to back of array to make room so that A[0:i-1] unpair to form A[0:2i-1]
for(int j=n/2-1;j>=i;--j)
swap(A[j],A[i+j]);
//unpair (above unimportant entries) [2i,i+n/2) to form [i+n/2,n) formula: f(j)=j-i+n/2
for(int j=i+n/2-1;j>=2*i;--j){
auto it=A[j].begin();
for(int k=0;k<A[j].size()/2;++k)
++it;
A[j-i+n/2].splice(A[j-i+n/2].begin(),A[j],it,A[j].end());//unpair
}
//unpair (important entries) A[0:i-1] unpair to form A[0:2i-1] formula: f(j)=i+j
//those entries are important because they contain the ith smallest elements (but may also contain other elements)
for(int j=0;j<i;++j){
auto it=A[j].begin();
for(int k=0;k<A[j].size()/2;++k)
++it;
A[i+j].splice(A[i+j].begin(),A[j],it,A[j].end());//unpair
}
//so that A[0:i-1] contains the i smallest of the i pairs
nth_element(A.begin(),A.begin()+i-1,A.begin()+2*i,[](list<T>&a,list<T>&b){return a.front()<b.front();});
}
}

int main(){
int n=16;
int i=3;//3 smallest
vector<list<int> >A{{9},{12},{7},{5},{-1},{19},{3},{2},{45},{18},{33},{6},{-35},{98},{111},{160}};
cout<<"input: ";
for_each(A.begin(),A.end(),[](list<int>&l){cout<<l.front()<<' ';});
cout<<endl;
SMALL_ORDER_STAT_SELECT(A,n,i);
cout<<i<<" smallest: ";
for_each(A.begin(),A.begin()+i,[](list<int>&l){cout<<l.front()<<' ';});
cout<<endl;
}
$$$$
`