Изменения
запятые
{{Определение
|definition=
=== Описание алгоритма ===
Будем использовать процедуру рассечения массива элементов из алгоритма сортировки [[Быстрая сортировка|QuickSort]]. Пусть нам надо найти <tex>k</tex>-ую порядковую статистику, а после рассечения опорный элемент встал на позицию <tex>m</tex>. Возможно три случая:
* '''k = m'''. Порядковая статистика найдена.
=== Код алгоритма ===
Ниже представлен код представленного алгоритма. При реализации, однако, вместо рекурсивных вызовов изменяются границы поиска статистики во внешнем цикле. В коде счититаемсчитаем, что процедура '''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> выбирается левая или правая половины (или вообще алгоритм завершает работу). Оценку проводим сверху, то есть, будем считать, что каждый раз выбирается большая половина.
Для довершения доказательства необходима проверка базы индукции, но она тривиальна: для выборки порядковой статистики из одного элемента сравнений не требуется: <tex>T(1) = 0 < 4</tex>. Итого, мы доказали, что <tex>T(n) \le 4n</tex>, следовательно, <tex>T(n) = O(n)</tex>
== Ссылки ==
* [http://en.wikipedia.org/wiki/BFPRT Selection algorithm — Wikipedia]
* Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.3: Minimum-Comparison Selection, pp.207–219.
