Главная Промышленная автоматика.

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 , и эту часть доказательства мы оставляем в качестве упражнения. Пусть Т{п) - время, затра-





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 [35] 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0037