5. Порядковые статистики
 

Задача вычисления порядковых статистик заключается в нахождении к-го наименьшего элемента в последовательности из n элементов. Эту задачу иногда называют задачей нахождения к-ой порядковой статистики. При к =1 задача сводится к нахождению наименьшего элемента последовательности, а при к =n наибольшего элемента и решается не более чем за О(n) шагов. Одно из очевидных решений задачи вычисления порядковых s статистик состоит в следующем: упорядочить исходную последовательность в порядке не убывания элементов и взять к-й элемент. При этом, однако, необходимо учитывать требования реальной задачи, в интересах которой вычисляются порядковые статистики.

Во-первых, может оказаться, что в упорядоченной последовательности ключи нескольких элементов (к-й, (к + 1)-й, ...)…] имеют одно и то же значение. Тогда необходимо учитывать, должны ли такие элементы следовать друг за другом в том же порядке, как и в исходной последовательности, или это необязательно. В первом случае упорядочение исходной последовательности необходимо выполнить одним из методов устойчивой сортировки, во втором случае можно использовать любой метод сортировки.
Во-вторых, отыскивается ли одна или несколько порядковых статистик. В зависимости от этого может стать выгодным применение того или иного алгоритма.
В-третьих, на выбор алгоритма влияет число элементов n исходной последовательности.

Наконец, если исходная последовательность должна быть сохранена без изменения, то для отыскания порядковых статистик придется создать копию исходной последовательности или массив ключей из элементов исходной последовательности. Использование массива ключей может оказаться выгодным и в том случае, когда элементы исходной последовательности имеют сложную структуру и их перестановки в процессе вычисления порядковых структур требуют значительного времени. Если требование устойчивой сортировки не обязательно, то можно применить рекурсивную процедуру, основанную на быстрой сортировке Хоара (Quicksort), которая обеспечивает самую быструю в среднем сортировку.

Отличие рекурсивной процедуры нахождения к-й порядковой статистики от процедуры быстрой сортировки Хоара заключается в том, что, во-первых, после разбиения на две группы выбирается та группа, в ко¬торой находится к-й элемент, и, во-вторых, в дальнейшем обрабатывается только эта группа, а не обе группы, как это делается в быстрой сортировке Хоара.

Время, затрачиваемое на нахождение к-й порядковой статистики как по одному методу так и по другому, зависит от удачного выбора опорного элемента при разбиении на группы. Время будет минимально, если при каждом проходе группы содержат примерно одинаковое число элементов. Доказано, что в том случае, если каждый проход осуществляется даже на множестве, составляющем 9/10 предыдущего, то время выполнения будет порядка О(n), а в худшем случае — не более О(n²). Линейный метод нахождения порядковых статистик, обеспечивает в самом худшем случае время выполнения порядка О(n). Этот метод основан на поиске «хорошего» опорного элемента и применяется для последовательностей с большим числом элементов.