1=/, И все время в Alf], . . ., Ali-l] будут находиться элементы из 5i. Аналогично вначале /=/, а в Л[/+11, . ., А[1] все время будут находиться элементы из SaUSa. Это разбиение производит подпрограмма на рис. 3.8.

Затем можно вызвать БЫСТРСОРТ для массива Л[/1, . . . .. ., /4[t-1], т. е. 5i, и для массива Л[у+1], . . ., А[1], т. е. Sa USg. Но если i=f (и тогда Si=0), то надо сначала удалить из S2US3 хотя бы один элемент, равный а. Удобно удалять тот элемент, по которому производилось разбиение. Следует также заметить, что если это представление в виде массива применяется для последовательностей, то можно подать аргументы для БЫСТРСОРТ, просто поставив указатели на первую и последнюю ячейку используемого куска массива.

Пример 3.5. Разобьем массив Л

по элементу а=3. while-оператор (строка 4) уменьшает / с 9 до 7, поскольку числа Л[9]=3 и Л[8]=8 оба не меньше а, но Л[7]=1<а. Строка 5 не увеличивает i с его начального значения 1, поскольку Л[1]=6>а. Поэтому мы переставляем Л[1] и Л [7], полагаем 1=2, /=6 и получаем массив на рис. 3.9, а. Результаты, получаемые после следующих двух срабатываний цикла в строках 3-9, показаны на рис. 3.9, бив. В этот момент г>/, и выполнение while-оператора, стоящего в строке 3, заканчивается. □

Рис. 3.9. Разбиение массива.

3.6. ПОРЯДКОВЫЕ СТАТИСТИКИ

С упорядочением тесно связана задача нахождения k-ro наименьшего элемента в я-элементной последовательности Одно из очевидных решений состоит в следующем: упорядочить эту последовательность в порядке неубывания ее элементов и взять k-й элемент. Как мы уже видели, это потребует п log п сравнений. Аккуратно применяя стратегию "разделяй и властвуй", можно найти k-й наименьший элемент за 0{п) шагов. Важный частный случай -/2= = Г п/2 ~]; в этом случае середина последовательности отыскивается за линейное время.

Алгоритм 3.6. Нахождение k-го наименьшего элемента

Вход. Последовательность 5 из п элементов, принадлежащих линейно упорядоченному множеству, и целое число k, lkn.

Вьаод. k-й наименьший элемент последовательности S.

Метод. Применяется рекурсивная процедура ВЫБОР, приведенная на рис. 3.10. □

Проанализируем алгоритм 3.6 на интуитивном уровне, чтобы увидеть, почему он работает, как надо. Основная идея - данная последовательность разбивается по некоторому элементу т на такие три подпоследовательности Si, Sj, S3, что Si содержит все элементы, меньшие т, S2- все элементы, равные т, и S3 - все элементы, большие т. Сосчитав число элементов в Si и S2, можно узнать, в каком из множеств Si, S2 и S3 лежит k-й наименьший элемент. Таким приемом можно свести данную задачу к меньшей.

Чтобы получить линейный алгоритм, надо уметь за линейное время находить разбивающий элемент так, чтобы длина каждой из подпоследовательностей Si и S2 была бы не больше фиксированной доли длины последовательности S. Вся хитрость в способе выбора разбивающего элемента т. Последовательность S разбивается на подпоследовательности по пять элементов в каждой. Каждая подпоследовательность упорядочивается, и из медиан всех этих подпоследовательностей составляется последовательность М. Теперь М содержит только п/5 J элементов, и можно найти ее медиану в пять раз быстрее, чем у последовательности из п элементов.

Далее, не меньше четверти всех элементов последовательности 5 не превосходят т, и не меньше четверти ее элементов больше или равны т. Это проиллюстрировано на рис. 3.11. Возникает вопрос: причем здесь "магическое число" 5? Ответ заключается в том, что процедура ВЫБОР рекурсивно вызывается два раза, каждый раз

) Строго говоря, k-m наименьшим элементом последовательности Oi, а, . а„ называется такой элемент b этой последовательности, что а,-<й не более чем для k-1 значений i и а;<6 не менее чем для k значений i. Например, 4 - второй и третий наименьший элемент последовательности 7, 4, 2, 4.

procedure ВЫБОР(/г, 5):

1. If S<50 then

begin

2. упорядочить 5;

3. return k-a наименьший элемент в S end

else begin

4. разбить S на L I "51/5 J последовательностей no 5 эле-

ментов в каждой;

5. при этом останется не более четырех неиспользован-

ных элементов;

6. упорядочить каждую пятиэлементную последователь-

ность;

7. пусть М-последовательность медиан этих пятиэлемент-

ных множеств;

8. mBbIBOP(rAf 1/21, М);

9. пусть Si, S2 и s3 -последовательности элементов из S,

соответственно меньших, равных и больших т;

10. If Si>/j then return ВЫБОР(/г, SJ else

11. If (\S,\ + \S,\k) then return m

12. else return ВЫБОР{/г- Sj - S , S,) end

Рис. 3.10. Алгоритм выбора k-то наименьшего элемента.

на последовательности, длина которой равна некоторой части длины последовательности S. Чтобы алгоритм работал линейное время, сумма длин этих двух последовательностей должна быть меньше \S\. Числа, отличные от 5, также годятся, но для некоторых из них процесс упорядочения подпоследовательностей будет дольше. В качестве упражнения предлагаем выяснить, какие же числа можно использовать вместо 5.

Теорема 3.9. Алгоритм 3.6 находит k-й наименьший элемент в п-элементной последовательности S за время 0{п).

Доказательство. Корректность алгоритма доказывается непосредственно индукцией по S , и эту часть доказательства мы оставляем в качестве упражнения. Пусть Т{п) - время, затра-