Необходимое изменение программы 2.11 касается лишь цасги, фиксирующей новые запросы. Она теперь имеет вид

if J-l < r-i then jgin if i < then

begin [записи запроса на сррпшровку правой части]

S := S+1; stack[s] Л := /; stack[s] .г г

-end;

г := J [продолжение сортировки левой части] .end else

begin if / <J then

begin [запись в стек.запроса на сортировку левой части) S := J+1; stackis] .1:- Ц siacls] .г :=*= /

end;

I := i [продолжение сортировки правой части]

(2.16)

2.2.7. Поиск медианы

Медианой последовательности из п элементов называется элемент, значение которого меньше (или равно) половины п элементов и больше (или равно) другой половины. Например, медиана

16 12 99 95 18 87 10

есть 18.

Задачу поиска медианы принято связывать с сортировкой, так как медиану всегда можно найти следующим способом: рассортировать п элементов и затем выбрать средний элемент. Но разделение, которое выполняет программа 2.9, позволяет потенциально найти медиану значительно быстрее. Рассматриваемый здесь метод дает возможность решать и более общую задачу поиска элемента с k-м по величине значением из п элементов. Поиск медианы является частным случаем для k - п/2.

Алгоритм, изобретенный К. Хоором [2.4], работает следующим образом. Прежде всего применяется операция раз-Деления, используемая при быстрой сортировке, с /==1, = п и с a[k], выбранным в качестве разделяющего значения (границы) X. Получаются значения индексов i и /, такие, что

1) а[А]л: для всех h<i,

2) a[h]x для всех Л >/, (2-17)

Возможны три варианта:

1. Разделяющее значение х было слишком мало; в резуль, тате граница между двумя частями ниже искомого значе-ния k. Процесс разбиения следует повторить для элемен. тов a[i], .... а [г] (см. рис. 2.9).

1 П I f

I / i к г

Рис. 2.9. Граница слишком низко.

2. Выбранная граница х была слишком велика. Операцию -разбиения следует повторить на подмасс^иве аЩ, (см. рис. 2.10).

I < I > I

1-}-п-г

/ к i i Г

Рис. 2.10. Граница слишком высоко.

3. Значение k лежит в интервале j <. k<Ci: элемент а [k] разделяет массив в заданной пропорции и, следовательно, является искомым (см. рис. 2.11).

т ггт--~~т

Рис. 2.11. Граница проведена правильно.

Процесс разбиения повторяется до появления случая 3. Этой итерации соответствует следующий фрагмент программы;

/:= 1; t:= п; while / < г do begin X := ф];

раптоп{а\1\...ф])1 -

if/< А: then/:=/; if к < i then г :=/

За формальным доказательством корректности этого алгоритма мы отсылаем читателя к статье Хоора, Теперь мы можем целиком написать всю программу Find.

ftoceuvaefind(к; integer);

Yflt l,r,i,j,w,xi integer; begin /: 1; г := и;

while / < г do

begin X := a[k]; i: /; у ; ; repeat {jjp/ft}

---- while < л: do f := i-fl;

while X < 4j] do 7 :==: j-l; if i then

begin r= И; fl[,] ф]; ф] и-; i:- :=y-l

end until i > j; if/< A: then/:= /; if < I then r := у

end [find]

Программа 2.12. Поиск k-го элемента.

Если предположить, что в среднем каждое разбиение уменьшает вдвое размер подмассива, в котором содержится искомый элемент, то число необходимых сравнений равно

-f + +... + l=2rt, (2.19)

т. е. порядка п. Этим объясняется эффективность программы Find при нахождении медиан и других квантилей и ее преимущество по сравнению с приходящим вначале в голову методом сортировки всего множества элементов для выбора fe-ro по величине (такой метод в лучшем случае дает порядок n-logn). Однако в худшем случае каждый шаг разбиения уменьшает размер множества, в котором ищется нужный элемент, только на 1, и поэтому требуется порядок сравнений. Следовательно, этот алгоритм тоже вряд ли стоит использовать для небольшого числа элементов (скажем, Меньше 10).

2.2.8. Сравнение методов сортировки массивов

В завершение нашего обзора -методов сортировки мы попытаемся сравнить их эффективность. Пусть п по-прежнему обозначает число сортируемых элементов, а С и М - соответственно количество необходимых сравнений ключей и