Структуры данных и алгоритмы (1021739), страница 67
Текст из файла (страница 67)
Для простоты временно положим, что все значения ключей различны (случай одинаковых ключевых значений будет рассмотрен ниже). Покажем, что выбранный опорный элемент (являющийся [(п + 5)/10]-м порядковым элементом среди [га/5] средних элементов) больше не менее 3[(га - 5)/10] элементов из гаисходных элементов. В самом деле, опорный элемент больше [(л - 5)/10] средних элементов. В свою очередь каждый из этих средних элементов больше двух элементов из той8.7. ПОРЯДКОВЫЕ СТАТИСТИКИ259пятерки элементов, которой он принадлежит.
Отсюда получаем величину 3[(га — 5)/10].Если га > 75, тогда 3[(га - 5)/10] не меньше ге/4. Подобным образом доказывается, чтовыбранный опорный элемент меньше или равен не менее 3[(га - 5)/10] элементов. Отсюда следует, что при п > 75 выбранный опорный элемент находится между первой ипоследней четвертями отсортированного списка исходных элементов.Алгоритм нахождения k-u порядковой статистики в виде функции select показанв листинге 8.14.
Как и в алгоритмах сортировки, предполагаем, что список исходныхэлементов представлен в виде массива А записей типа recordtype и что записи имеютполе key типа key type. Нахождение k-u порядковой статистики выполняется, естественно, посредством вызова функции select(l, n, k).Листинг 8.14. Линейный алгоритм нахождения Ar-й порядковой статистикиfunction select (i, j, k: integer ): keytype;{ Функция возвращает значение ключа k-ro элементаиз Л[1], ..., A[j] }var(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)т: integer; { используется в качестве индекса }beginif j - i < 74 then begin{ элементов мало, select рекурсивно не применяется }сортировка A[i], ..., A[j] простым алгоритмом;return(A[i + k - I].key)endelse begin { select применяется рекурсивно }for m:= 0 to ( j - i - 4 ) div 5 do{ нахождение средних элементов в группахиз 5-ти элементов }нахождение 3-го по величине элемента в группеA[i + 5*т], ....
A[i + 5*т + 4] иперестановка его с A[i + т];pivot:= select(i,i+(j-i-4) div 5,(j-i-4) div 10);{ нахождение медианы средних элементов }т: = partitiond, j, pivot);if k <= т - i thenreturn(select(i, т - I , k))elsereturn(select (m, j, k - (m - i) ))endend; { select }Для анализа времени выполнения процедуры select из листинга 8.14 положимздесь, что j — i + 1 = га. Строки (2), (3) выполняются, если п не превосходит 74. Поэтому, если даже выполнение строки (2) требует времени порядка О(п2) в общем случае, здесь потребуется конечное время, не превосходящее некоторой константы с.Таким образом, при п < 74 строки (1) — (3) требуют времени, не превосходящего некоторой константы с\.Теперь рассмотрим строки (4) - (10).
Строка (7), разбиение множества элементовпо опорному элементу, имеет время выполнения О(п), как было показано при анализе алгоритма быстрой сортировки. Тело цикла (4), (5) выполняется п/5 раз, упорядочивая за каждую итерацию 5 элементов, на что требуется фиксированное время. Поэтому данный цикл выполняется за время порядка О(п).Обозначим через Т(п) время выполнения процедуры select на п элементах.
Тогдастрока (6) требует времени, не превышающего Т(п/5). Поскольку строку (10) можнодостигнуть только для га > 75, а, как было показано ранее, при п > 75 количествоэлементов, меньших опорного элемента, не превышает Зга/4. Аналогично, количество260ГЛАВА 8. СОРТИРОВКАэлементов, больших или равных опорному элементу, не превышает Зл/4. Следовательно, время выполнения строки (10) не превышает Т(Зга/4). Отсюда вытекает, чтодля некоторых констант GI и с2 справедливы неравенства7Чга)<{ С1>если га < 74,[с2п + Т(п 15) + Т(3п 14), если п > 75.В неравенствах (8.15) выражение с2п представляет время выполнения строк (1),(4), (5) и (7), выражение Г(л/5) соответствует времени выполнения строки (6), а7X3/1/4) — строк (9), (10).Далее мы покажем, что Т(п) из (8.15) имеет порядок О(п).
Но сначала несколькослов о "магическом числе" 5, размере групп в строке (5) и условии п < 75, котороеопределяет способ нахождения порядковой статистики (посредством рекурсивногоповторения функции select или прямым способом). Конечно, эти числа могут быть идругими, но в данном случае они выбраны так, чтобы в формуле (8.15) выполнялосьнеравенство 1/5 + 3/4 < 1, необходимое для доказательства линейного порядка величины Т(п).Неравенства (8.15) можно решить методом индукции по п. Предполагаем, что решение имеет вид сп для некоторой константы с.
Если принять с > съ тогда Т(п) < спдля всех га от 1 до 74, поэтому рассмотрим случай, когда га > 75. Пусть, в соответствии с методом математической индукции, T(m) < cm для всех т, т < п. Тогда из(8.15) следует, чтоТ(п) < сгп + сга/5 + Зсп/4 < С2га + 19сга/20.(8.16)Еслиположитьс — тах(с!, 20с2),тогдаиз(8.16)получаемТ(п) < сп/20 + сп/5 + Зсп/4 = сп, что и требовалось доказать. Таким образом, Т(п)имеет порядок О(га).Случай равенства некоторых значений ключейНапомним, что при создании процедуры листинга 8.14 мы предполагали, что всезначения ключей различны. Это сделано из-за того, что в противном случае нельзядоказать, что множество элементов при разбиении распадется на подмножества, непревышающие Зга/4. Для возможного случая равенства значений ключей необходимотолько немного изменить функцию select из листинга 8.14.
После строки (7), выполняющей разбиение множества, надо добавить операторы, собирающие вместе все записи, имеющие значения ключей, совпадающих с опорным элементом. Пусть такихключей будет р > 1. Если m-j<k<m-i+p, тогда в последующем рекурсивномвызове функции select нет необходимости — достаточно вернуть значение A[m].key. Впротивном случае строка (8) остается без изменений, а в строке (10) осуществляетсявызов select(m + р, j, k — (тп - i) — р).Упражнения8.1.Есть восемь целых чисел 1, 7, 3, 2, 0, 5, 0, 8.
Выполните их упорядочиваниес помощью метода "пузырька", сортировки вставками, сортировки посредством выбора.Есть шестнадцать целых чисел 22, 36, 6, 79, 26, 45, 75, 13, 31, 62, 27, 76, 33,16, 62, 47. Трактуя каждое число как пару цифр из интервала 0-9, выполнитеих упорядочивание, используя быструю сортировку, сортировку вставками,пирамидальную сортировку и "карманную" сортировку.Процедура Shellsort (сортировка Шелла1), показанная в листинге 8.15, сортирует элементы массива А[1..п] следующим образом: на первом шаге упорядочиваются элементы га/2 пар (A[i], А[га/2 + i]) для 1 < i < л/2, на втором8.2.8.3.1Этот метод сортировки часто называют сортировкой с убывающим шагом.УПРАЖНЕНИЯ261шаге упорядочиваются элементы(A[i], A[n/4 + i], A[n/2 + i ] , A[3n/4упорядочиваются элементы в л/8последнем шаге упорядочиваютсякаждом шаге для упорядочиванияки вставками.i,->:',: ':•..-'.:'•.', . ; .
" i.'i:Листинг 8.15. Сортировка Шеллав л/4 группах из четырех элементов+ {]) для 1 < i < л/4, на третьем шагегруппах из восьми элементов и т.д. Наэлементы сразу во всем массиве А. Наэлементов используется метод сортиров:'. '••; •S;.:'::.procedure Shellsort ( var A: array[1..л] of integer );vari, j, incr: integer;beginincr:= n div 2;while incr > 0 do beginfor i:= incr + 1 to n do beginj : = i - incr;while j > 0 doif A [ j ] > A ( j + incr] then begins\ifap(A[j] , A[j + incr]);j:= j - increndelsej : = 0 { останов }end;iincr:= incr div 2endend; { Shellsort }а) с помощью сортировки Шелла выполните упорядочивание последовательностей целых чисел из упражнений 8.1 и 8.2;*б) покажите, что если элементы A[i] и А[л/2* + i]) упорядочены (переставлены) на k-м.
шаге, то они останутся упорядоченными и на следующем(k + 1)-м шаге;в) в листинге 8.15 использовалась убывающая последовательность шагов л/2,л/4, л/8, ..., 2, 1. Покажите, что алгоритм Шелла работает с любой убывающей последовательностью шагов, у которой последний шаг равен 1;**г) покажите, что время выполнения алгоритма Шелла имеет порядок О(ль5).*8.4. Предположим, что необходимо сортировать список элементов, состоящий изуже упорядоченного списка, который следует за несколькими "случайными"элементами. Какой из рассмотренных в этой главе методов сортировки наиболее подходит для решения такой задачи?*8.5.
Алгоритм сортировки называется устойчивым, если он сохраняет исходныйпорядок следования элементов с одинаковыми значениями ключей. Какой изалгоритмов сортировки, представленных в этой главе, устойчив?*8.6. Предположим, что в алгоритме быстрой сортировки в качестве опорного элемента выбирается первый элемент сортируемого подмножества.а) какие изменения следует сделать в алгоритме быстрой сортировки(листинг 8.8), чтобы избежать "зацикливания" (бесконечного цикла) в случае последовательности равных элементов?б) покажите, что измененный алгоритм быстрой сортировки в среднем будетиметь время выполнения порядка О(л logra).262ГЛАВА 8.
СОРТИРОВКА8.7.Покажите, что любой алгоритм сортировки, перемещающий за один шаг только один элемент и только на одну позицию, должен иметь временною сложность не менее П(п2).8.8.В алгоритме пирамидальной сортировки процедура pushdown из листинга 8.10строит частично упорядоченное дерево за время О(п). Вместо того чтобы начинать построение дерева от листьев, начните построение от корня.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
