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

элементов, больших или равных опорному элементу, не превышает Зге/4. Следовательно, время выполнения строки (10) не превышает Т(Зп/4). Отсюда вытекает, что для некоторых констант ci и справедливы неравенства

гт, fcj, еслИря 74

[с2П+ Г(л/5) + Т(3п/А), если л > 75.

В неравенствах (8.15) выражение сзл представляет время выполнения строк (1), (4), (5) и (7), выражение Т(п/Ъ) соответствует времени выполнения строки (6), а Т(Зл/4) - строк (9), (10).

Далее мы покажем, что 7(л)из (8.15) имеет порядок 0(л). Но сначала несколько слов о "магическом числе" 5, размере групп в строке (5) и условии п < 75, которое определяет способ нахождения порядковой статистики (посредством рекурсивного повторения функции select или прямым способом). Конечно, эти числа могут быть и другими, но в данном случае они выбраны так, чтобы в формуле (8.15) выполнялось неравенство 1/5 -I- 3/4 < 1, необходимое для доказательства линейного порядка величины Т(п).

Неравенства (8.15) можно решить методом индукции по п. Предполагаем, что решение имеет вид сп для некоторой константы с. Если принять с > Ci, тогда T{ii)< сп для всех га от 1 до 74, поэтому рассмотрим случай, когда га > 75. Пусть, в соответствии с методом математической индукции, Т(т) < cm для всех т, т < п. Тогда из (8.15) следует, что

Т(п)< Сзл -I- сл/5 -I- Зсл/4 < СзЛ -I- 19сл/20. (8.16)

Если положить с - max(ci, ЗОс), тогда из (8.16) получаем

Т(п) < сл/20-l- сп/5 -I- Зсп/4 = сп, что и требовалось доказать. Таким образом, Т(п) имеет порядок 0(л).

Случай равенства некоторых значений ключей

Напомним, что при создании процедуры листинга 8.14 мы предполагали, что все значения ключей различны. Это сделано из-за того, что в противном случае нельзя доказать, что множество элементов при разбиении распадется на подмножества, не превышающие Зга/4. Для возможного случая равенства значений ключей необходимо только немного изменить функцию select из листинга 8.14. После строки (7), выполняющей разбиение множества, надо добавить операторы, собирающие вместе все записи, имеющие значения ключей, совпадающих с опорным элементом. Пусть таких ключей будет р > \. Если m-j<k<m-i+p, тогда в последующем рекурсивном вызове функции select нет необходимости - достаточно вернуть значение А[т].кеу. В противном случае строка (8) остается без изменений, а в строке (10) осуществляется вызов select{m + p,j,k - (m-i)- р).

Упражнения

8.1. Есть восемь целых чисел 1, 7, 3, 2, О, 5, О, 8. Выполните их упорядочивание с помощью метода "пузырька", сортировки вставками, сортировки посредством выбора.

8.2. Есть шестнадцать целых чисел 22, 36, 6, 79, 26, 45, 75, 13, 31, 62, 27, 76, 33, 16, 62, 47. Трактуя каждое число как пару цифр из интервала 0-9, выполните их упорядочивание, используя быструю сортировку, сортировку вставками, пирамидальную сортировку и "карманную" сортировку.

8.3. Процедура Shellsort (сортировка Шелла), показанная в листинге 8.15, сортирует элементы массива Л[1.. л] следующим образом: на первом шаге упорядочиваются элементы га/2 пар (A[i], А[п/2 + i]) для 1 < ; < л/2, на втором

Этот метод сортировки часто называют сортировкой с убывающим шагом. УПРАЖНЕНИЯ 261



щаге упорядочиваются элементы в л/4 группах из четырех элементов (A[i],A[n/4 + ij, A[n/2 + ij, A[3n/4 + (\) для 1 < i < л/4, на третьем шаге упорядочиваются элементы в л/8 группах из восьми элементов и т.д. На последнем щаге упорядочиваются элементы сразу во всем массиве А. На каждом щаге для упорядочивания элементов используется метод сортировки вставками.

Листинг 8.15. Сортировка Шелла

procedure Shellsort { var А: array[l..n] of integer ) ; var

1, j, incr: integer; begin

lncr:= n div 2;

while incr > О do begin

for i: = incr -b 1 to n do begin J : = i - incr; while у > 0 do

ifAfJJ >A(J + incr] then begin swap(A{j\ АЦ + incr] ) ; j:= j - incr

end else

j:= 0 { останов }

end;

incr:= incr div 2

end; { Shellsort}

a) с помощью сортировки Шелла выполните упорядочивание последовательностей целых чисел из упражнений 8.1 и 8.2;

*б) покажите, что если элементы АЦ] и Л[п/2 -i- г]) упорядочены (переставлены) на fe-M щаге, то они останутся упорядоченными и на следующем (fe + 1)-м шаге;

в) в листинге 8.15 использовалась убывающая последовательность щагов л/2, л/4, л/8, 2, 1. Покажите, что алгоритм Шелла работает с любой убывающей последовательностью щагов, у которой последний щаг равен 1;

**г) покажите, что время выполнения алгоритма Шелла имеет порядок 0(ге). *8.4. Предположим, что необходимо сортировать список элементов, состоящий из уже упорядоченного списка, который следует за несколькими "случайными" элементами. Какой из рассмотренных в этой главе методов сортировки наиболее подходит для рещения такой задачи?

*8.5. Алгоритм сортировки называется устойчивым, если он сохраняет исходный порядок следования элементов с одинаковыми значениями ключей. Какой из алгоритмов сортировки, представленных в этой главе, устойчив?

*8.6. Предположим, что в алгоритме быстрой сортировки в качестве опорного элемента выбирается первый элемент сортируемого подмножества.

а) какие изменения следует сделать в алгоритме быстрой сортировки (листинг 8.8), чтобы избежать "зацикливания" (бесконечного цикла) в случае последовательности равных элементов?

б) покажите, что измененный алгоритм быстрой сортировки в среднем будет иметь время выполнения порядка 0(п logre).



8.7. Покажите, что любой алгоритм сортировки, перемещающий за один шаг только один элемент и только на одну позицию, должен иметь временн(/ю сложность не менее П(п).

8.8. В алгоритме пирамидальной сортировки процедура pushdown из листинга 8.10 строит частично упорядоченное дерево за время 0(п). Вместо того чтобы начинать построение дерева от листьев, начните построение от корня. Какова в этом случае будет временная сложность процедуры построения частично упорядоченного дерева?

*8.9. Допустим, что есть множество слов, т.е. строк, состоящих из букв а - г. Суммарная длина слов равна п. Покажите, что эти слова можно упорядочить за время 0(п). Отметим, что для слов одинаковой длины можно применить "карманную" сортировку. Но вы также должны предусмотреть случай слов разной длины.

*8.10. Покажите, что для сортировки вставками среднее время выполнения не меньше ii(n).

**8.11. Рассмотрим алгоритм случайной сортировки, примененный к массиву А[1..п] целых чисел: выбирается случайное число i из интервала от 1 до л и меняются местами элементы А[1] и A[i], процесс повторяется до тех пор, пока не будут упорядочены все элементы массива. Каково ожидаемое время выполнения этой сортировки?

*8.12. В разделе 8.6 было показано, что сортировки, выполняемые посредством сравнений, в самом худшем случае требуют Q(n logn) сравнений. Покажите, что эта нижняя граница справедлива и в среднем.

*8.13. Докажите, что процедура select, неформально описанная в начале раздела 8.7, имеет среднее время выполнения 0(п).

8.14. Реализуйте оператор конкатенации CONCATENATE для структуры данных, показанной на рис. 8.4.

8.15. Напишите программу нахождения к наименьших элементов в массиве длиной п. Какова временная сложность этой программы? Для каких значений к эффективнее сначала выполнить сортировку всего массива, а затем взять к наименьших элементов, вместо поиска наименьших элементов в неупорядоченном массиве?

8.16. Напишите программу нахождения наибольшего и наименьшего элементов в массиве. Может ли эта программа обойтись менее чем 2га - 3 сравнениями?

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

*8.18. Покажите на модели дерева решений из раздела 8.6, что любой алгоритм удаления дублирующих записей из заданного списка требует времени не менее Q(n logn).

*8.19. Предположим, что есть к множеств Si, S2 St, каждое из которых состоит из га действительных чисел. Напишите программу получения списка всех сумм вида 5i + «2 + ••• + где принадлежит отсортированному множеству Sj. Какова временная сложность этой программы? 8.20. Предположим, есть сортированный массив строк Si, S2, s„. Напишите программу, определяющую, является ли предъявленная строка х членом этой последовательности. Какова временная сложность этой программы как функции от ц и длины строки х7





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

0.0041