Изменения
→Описание алгоритма
{{Определение
|definition=
* '''k = m'''. Порядковая статистика найдена.
* '''k < m'''. Рекурсивно ищем <tex>k</tex>-ую статистику в первой половине части массива.* '''k > m'''. Рекурсивно ищем <tex>(k - m - 1)</tex>-ую статистику во второй половине части массива.
=== Код алгоритма ===
Ниже представлен код представленного алгоритма. При реализации, однако, вместо рекурсивных вызовов изменяются границы поиска статистики во внешнем цикле. В коде счититаемсчитаем, что процедура '''partition''' принимает массив и границы отрезка, который будет рассечён (причём правая граница отрезка не включается) , и возвращает индекс опорного элемента. Также, считается, что массив индексируется с нуля.
'''int''' findOrderStatistic('''int[]''' array, '''int''' k) {
}
'''else''' {
left = mid + 1;
}
=== Анализ времени работы ===
Аналогично QuickSort, может возникнуть такой же худщий худший случай (процедура '''partition''' возвращает каждый раз левую или правую границу рассматриваемой части), при котором время работы составит <tex>\Omega(n^2)</tex>. Однако, если считать, что '''partition''' возвращает все элементы рассматриваемого отрезка с равной вероятностью, то можно оценить матожидание времени работы как <tex>O(n)</tex>.
Будем оценивать количество сравнений. При поиске статистики в массиве размера <tex>n</tex> функция '''partition''' (точнее, одна из распространённых вариаций) совершает не более <tex>n - 1</tex> сравнений. Далее, в зависимости от <tex>k</tex> выбирается левая или правая половины (или вообще алгоритм завершает работу). Оценку проводим сверху, то есть, будем считать, что каждый раз выбирается большая половина.
