K-th order statistic in O (N)

Suppose we are given an array A of length N, and suppose given the number of K. The challenge is to find in the array K-th largest number, ie K-th order statistics.



The basic idea - the idea of ​​using quicksort. Actually, the algorithm is simple, difficult to prove that he works an average of O (N), in contrast to the quick sort.



The implementation in the form of non-recursive function:

template <class T>
T order_statistics (std :: vector <T> a, unsigned n, unsigned k)
{
using std :: swap;
for (unsigned l = 1, r = n;;)
{

if (r <= l +1)
{
/ / The current part consists of one or two elements -
/ / Can easily find the answer
if (r == l +1 && a [r] <a [l])
swap (a [l], a [r]);
return a [k];
}

/ / Sort a [l], a [l +1], a [r]
unsigned mid = (l + r) >> 1;
swap (a [mid], a [l +1]);
if (a [l]> a [r])
swap (a [l], a [r]);
if (a [l +1]> a [r])
swap (a [l +1], a [r]);
if (a [l]> a [l +1])
swap (a [l], a [l +1]);

/ / Do the division
/ / Barrier is a [l +1], ie the median of a [l], a [l +1], a [r]
unsigned
i = l +1,
j = r;
const T
cur = a [l +1];
for (; ;)
{
while (a [+ + i] <cur);
while (a [- j]> cur);
if (i> j)
break;
swap (a [i], a [j]);
}

/ / Insert a barrier
a [l +1] = a [j];
a [j] = cur;

/ / Continue to work in that part
/ / Which should contain the desired element
if (j> = k)
r = j-1;
if (j <= k)
l = i;

}
}