Хай маємо множину (масив) з n чисел.
Найочевидніше, і найпростіше рішення — відсортувати масив, і після цього будь-яку порядкову статистику можна знаходити за одиничний час. Це хороше рішення, якщо нам потрібно шукати багато різних статистик одного масиву. Правда сортування масиву займає час мінімум O(n log(n)).
З усім тим, в багатьох задачах порядкову статистику потрібно знайти лише раз. І це можна зробити за лінійний час. Пошук мінімуму або максимуму — тривіальна задача:
int min(int *a, int l, int r)
{
int m=l;
for(int i=l+1;i<=r;i++)
{
if(a[i]<a[m]) m=i;
}
return a[m];
}
Але не сортуючи масив можна знайти й будь-яку іншу порядкову статистику. Секрет в тому, що масив сортується, але не повністю. Розглянемо швидке сортування.
void qsort(int *a, int l, int r)
{
if(l>=r) return;
int c=partition(int *a, int l, int r);
qsort(a,l,c);
qsort(a,c+1,r);
}
Спочатку масив ділять на дві частини, де всі елементи лівої частини менші за будь-який з правої. Ми знаємо, що в лівій частині c елементів. Тому, якщо i — номер елемента якого ми шукаємо, то він знаходиться в лівій частині, якщо інакше він знаходиться в правій частині, але при пошуку в правій частині не забуваємо, що зліва є c менших елементів. Спробуємо написати функцію пошуку порядкової статистики використавши ці міркування:
int nth_element(int *a, int l, int r, int n)
{
if(l=r) return a[l];
int c=partition(int *a, int l, int r);
int k=c-l+1;
if(n<=k) return nth_element(a,l,c,n);
else return nth_element(a,c+1,r, n-k);
}