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