Быстрый поиск порядковой статистики

[Andrey_Kireew]

Здравствуйте. Возникла такая задача: из массива N действительных чисел найти k-е число упорядоченной последовательности.
Пока я применил брутальное решение, основанное на предварительной сортировке:

Используется синтаксис C

// ys - сортируемый массив 
.....................................
const int Lag[9]={1, 4, 10, 23, 57, 132, 301, 701, 1750};
    int N=8, j, Lim;
    double val;
    
    if (nObs==1) return 0;
    
    while (Lag[N] >= nObs) N--;
       
    for (int ii=N; ii>=0; ii--)
    { Lim=Lag[ii];
      for (int pos=Lim; pos < nObs; pos++)
      {
        val=*(ys+pos);
        for (j=pos; j>=Lim; j-=Lim)
            if (val<*(ys+j-Lim))
                *(ys+j)=*(ys+j-Lim);
            else
                break;
            
        *(ys+j)=val; 
      }
    }

val=*(ys+k);
........................
 

Однако есть подозрение, что можно сделать эффективнее, т.к. сортировка всех элементов массива не требуется.
Видел соответствующие адаптации алгоритма quksort, но они меня не очень впечатлили, т.к. в том виде, как они есть - весьма неустойчивы и могут деградировать до $O(N^2)$.
Хотелось бы обсудить, как это можно реализовать лучше, проще и эффективнее.

[iifat]

Может, пирамидальную? Первую стадию провести, вторую частично.
Если $k$ сравнительно маленькое, можно завести массив из $k$ элементов и одним проходом найти $k$ первых.

[Yuri Gendelman]

Например:
K’th Smallest/Largest Element in Unsorted Array
(На странице есть ссылки на предыдущие статьи серии.)

[venco]

В STL есть готовая функция:
https://en.cppreference.com/w/cpp/algorithm/nth_element

[Andrey_Kireew]

Спасибо Yuri Gendelman, кажется хорошая штука! Сейчас буду разбираться.

[Andrey_Kireew]

Ознакомился, и чуда не произошло. Там описан алгоритм, работающий за линейное время. Но, как часто бывает, константа слишком велика, что делает его на практике неэффективным. Опять же резюмируют, что лучший вариант - quksort с рандомизацией.
Но рандомизация мне вообще говоря не нравится. Плюсы от её применения, на мой взгляд, иллюзорны. Ведь нет ни какой гарантии, что после её применения элементы массива не распределяться ещё хуже.

[Dmitriy40]

Гарантии нет, но они если и станут хуже, то скорее всего незначительно. Зато аномально часто встречающийся худший случай превратится в произвольный (не самый худший), что и даст в среднем выигрыш. Если все входные комбинации равновероятны, то рандомизация лишняя.
Для гарантий применяйте методы класса $O(n \log n)$ в худшем случае.

[Andrey_Kireew]

Вообще, хотелось бы просто улучшить мою исходную сортировку Шелла, она хоть и не $n\cdot log(n)$, но всё равно прилично. Смущает тот факт, что она полностью сортирует весь массив ...