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

swapiAlr] , A[2*r + 1] ) ; r:= 2*r + 1

else { элемент в позиции г не нарушает порядок в частично упорядоченном дереве } г:= last { выход из цикла while }.

end; { pushdown }

Вернемся к листингу 8.9 и займемся строками (4) - (6). Выбор минимального элемента в строке (4) прост - это всегда элемент А[1]. Чтобы исключить оператор печати в строке (5), мы поменяли местами элементы А[1] и j4[i] в текушей куче. Удалить минимальный элемент из текушей кучи также легко: надо просто уменьшить на единицу курсор i, указываюший на конец текушей кучи. Затем надо вызвать процедуру pusAdou;n(l, i - 1) для восстановления порядка в частично упорядоченном дереве кучи А[1], A[i - 1].

Вместо проверки в строке (3), не является ли множество S пустым, можно проверить значение курсора /, указываюшего на конец текушей кучи. Теперь осталось рассмотреть способ выполнения операторов в строках (1), (2). Можно с самого начала поместить элементы списка L в массив А в произвольном порядке. Для создания первоначального частично упорядоченного дерева надо последовательно вызывать процедуру pushdown(i, п) для всех j = л/2, л/2 - 1, 1. Легко видеть, что после вызова процедуры pushdownij, п) порядок в ранее упорядоченной части строяшегося дерева не нарушается, так как новый элемент, добавляемый в дерево, не вносит нового нарушения порядка, поскольку он только меняется местами со своим "меньшим" сьшом. Полный код процедуры Aeapsort (пирамидальная сортировка) показан в листинге 8.11.

Листинг 8.11. Процедура пирамидальной сортировки

procedure heapsort ;

{ Сортирует элементы массива А [ 1 ] , А[п1

в убывающем порядке }

i: integer; { курсор в массиве А } begin

{ создание частично упорядоченного дерева } {1) for 1:= л div 2 downto 1 do

(2) pushdown (1, n) ;

(3) for i: - n downto 2 do begin

(4) swap(A[U . A[i-[ ) ;

{ удаление минимального элемента из кучи }

(5) pushdown (1 г i - 1)

{ восстановление частично упорядоченного дерева }

end; { heapsort }

Анализ пирамидальной сортировки

Сначала оценим время выполнения процедуры pushdown. Из листинга 8.10 видно, что тело цикла while (т.е. отдельная итерация этого цикла) выполняется за фиксированное время. После каждой итерации переменная г по крайней мере вдвое увеличивает свое значение. Поэтому, учитывая, что начальное значение г равно first, после ( итераций будем иметь г > first * 2. Цикл while выполняется до тех пор, пока г > last/2. Это условие будет выполняться, если выполняется неравенство first * 2 > last/2. Последнее неравенство можно переписать как

(• > \os(.iast/firsty 1. (8.8)



Следовательно, число итераций цикл while в процедуре pushdown не превышает log(last/first).

Поскольку first > 1 и last < п, то из (8.8) следует, что на каждый вызов процедуры pushdown в строках (2) и (5) листинга 8.11 затрачивалось время, по порядку не большее, чем O(logn). Очевидно, что цикл for строк (1), (2) выполняется п/2 раз. Поэтому обш;ее время выполнения этого цикла имеет порядок 0(п logn). Цикл в строках (3) - (б) выполняется п - 1 раз. Следовательно, на выполнение всех перестановок в строке (4) тратится время порядка 0(п), а на восстановление частично упорядоченного дерева (строка (5)) - 0(п logn). Отсюда вытекает, что обш;ее время выполнения цикла в строках (3) - (б) имеет порядок 0(п logn) и такой же порядок времени выполнения всей процедуры heapsort.

Несмотря на то что процедура heapsort имеет время выполнения порядка 0(п logn) в самом худшем случае, в среднем ее время несколько хуясе, чем в быстрой сортировке, хотя и имеет тот же порядок. Пирамидальная сортировка интересна в теоретическом плане, поскольку это первый рассмотренный нами алгоритм, имеюш;ий в самом худшем случае время выполнения 0(п logn). В практических ситуациях этот алгоритм полезен тогда, когда надо не сортировать все п элементов списка, а только отобрать к наименьших элементов, и при этом к значительно меньше п. В последнем примечании указывалось, что в действительности время выполнения цикла в строках (1), (2) имеет порядок 0(п). Если надо сделать только к итераций цикла (3) - (5), то на это потратится время порядка 0{k logn). Поэтому отбор к минимальных элементов процедура heapsort выполнит за время порядка 0(п + к logn). Отсюда следует, что при к < n/logn на выполнение этой операции потребуется время порядка 0(п).

8.5. „Карманная сортировка

Правомерен вопрос: всегда ли при сортировке п элементов нижняя граница времени выполнения имеет порядок П(п logn)? В следуюш;ем разделе мы рассмотрим алгоритмы сортировки и их нижнюю границу времени выполнения, если о типе данных ключей не предполагается ничего, кроме того, что их можно упорядочить посредством некой функции, цоказываюш;ей, когда один ключ "меньше чем" другой. Часто можно получить время сортировки меньшее, чем 0(п logn), но необходима дополнительная информация о сортируемых ключах.

Пример 8.5. Предиолологм, что значения ключей являются целыми числами из интервала от 1 до и, они не повторяются и число сортируемых элементов также равно п. Если обозначить через и В массивы типа аггау[1..ц] of recordtype, n элементов, цодлежаш;их сортировке, первоначально находятся в массиве А, тогда можно организовать поочередное цомеш;ение в массив В записей в порядке возрастания значений ключей следуюш;им образом:

for 1 := 1 to л do

B[A[i] .key] : = A[i] ; (8.9)

Этот код вычисляет, где в массиве В должен находиться элемент A[i], и цомеш;ает его туда. Весь этот цикл требует времени порядка 0(п) и работает корректно только тогда, когда значения всех ключей различны и являются целыми числами из интервала от 1 до п.

Более точный анализ показывает, что это время имеет порядок 0(п). Для i из интервала от п/2 до л/4 + 1 из (8.8) следует, что в процедуре pushdown цикл while выполняется не более одного раза. Для i из интервала от л/4 до п/8 + выполняются не более двух итераций и т.д. Поэтому общее количество итераций этого цикла для i из интервала от п/2 до 1 ограничено величиной 1*п/4 + 2*п/8 + 3*л/16 + .... С другой стороны, эта улучшенная оценка не влияет на время выполнения процедуры heapsort в целом, так как здесь основное время тратится на выполнение строк (3) - (5).

8.5. "КАРМАННАЯ" СОРТИРОВКА 247



Существует другой способ сортировки эдементов массива А с временем 0(п), но без использования второго массива В. Поочередно посетим элементы А[1], А[п]. Если запись в ячейке AfiJ имеет ключ j nj Ф i, то меняются местами записи в ячейках A[i] и A[j]. Если после этой перестановки новая запись в ячейке A[i] имеет ключ к я к Ф i, т осуществляется перестановка между A[i] и A[k] и т.д. Каждая перестановка помещает хотя бы одну запись в нркном порядке. Поэтому данный алгоритм сортировки эдементов массива А на месте имеет время выполнения порядка 0(п).

for j.:- 1 to И do

while .key <> i do

swap{A[i], AlAll] .key]) ;

Программа (8.9) - это простой пример "карманной" сортировки, где создаются "карманы" для хранения записей с определенным значением ключа. Мы проверяем, имеет ди данная запись ключ со значением г, и если это так, то помещаем эту запись в "карман" для записей, чьи значения ключей равны г. В программе (8.9) "карманами" являются элементы массива В, где B[i] - "карман" для записей с ключевым значением i. Массив в качестве "карманов" мокно использовать только в простейшем случае, когда мы знаем, что не может быть более одной записи в одном "кармане". Более того, при использовании массива в качестве "карманов" не возникает необходимости в упорядочивании эдементов внутри "кармана", так как в одном "кармане" содержится не более одной записи, а алгоритм построен так, чтобы элементы в массиве располагались в правильном порядке.

Но в общем случае мы должны быть готовы к тому, что в одном "кармане" может храниться несколько записей, а также должны уметь объединять содержимое нескольких "карманов" в один, располагая элементы в объединенном "кармане" в правильном порядке. Для определенности далее будем считать, что элементы массива имеют тип данных recordtype, а ключи записей - тип keytype. Кроме того, примем, но только в этом разделе, что тип данных keytype является перечисдимым типом, т.е. таким, как последовательность целых чисел 1, 2, п, иди как символьные строки. Обозначим через listtype (тип списка) тип данных, который представляет списки эдементов типа recordtype. Тип listtype может быть любым типом списков, описанным в главе 2, но в данном случае нам наиболее подходят связанные списки, поскольку мы будем их наращивать в "карманах" до размеров, которые нельзя предусмотреть заранее. Можно только предвидеть, что общая длина всех списков фиксирована и равна п, поэтому при необходимости массив из п ячеек может обеспечить реализацию списков для всех "карманов".

Необходим также массив В типа array[keytype] of listtype. Это будет массив "карманов", хранящих списки (иди заголовки списков, если используются связанные списки). Индексы массива В имеют тип данных keytype, так что каждая ячейка этого массива соответствует одному значению ключа. Таким образом, мы уже можем обобщить программу (8.9), поскольку теперь "карманы" имеют достаточную емкость.

Рассмотрим, как мокно выполнить объединение "карманов". Формально над списками Oi, о, и Ь\, Ьа, Ь, надо выполнить операцию конкатенации списков, в результате которой подучим список Ui, а,, bi, Ь, bj. Для реализации оператора конкатенации CONCATENATE(I.j, L), который заменяет список Ly объединенным списком L1L2, мокно использовать любые представления списков, которые мы изучали в главе 2.

Для более эффективного выполнения оператора конкатенации в добавление к заголовкам списков можно использовать указатели на последние элементы списков (иди на заголовок списка, если список пустой). Такое нововведение позволит избежать просмотра всех эдементов списка для нахождения последнего. На рис. 8.4 пунктирными линиями показаны измененные указатели при конкатенации списков Li и L2 в один общий список L]. Список после объединения списков предполагается "уничтоженным", поэтому указатели на его заголовок и конец "обнуляются".





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.002