Главная  Терминология Хоора 

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

J 3 2- Естественное слияние

В случае простого слияния мы ничего не выигрываем, если нные уже частично рассортированы. На -м проходе длина ех сливаемых подпоследовательностей меньше нли равна 2* учета того, что более длинные подпоследовательности уже огут быть упорядочены и их можно было бы сливать. Фактически можно было бы сразу сливать какие-либо упорядочен-~яые нодпосяедовательности длиной типе одну последовательность из m -- ft элементов. Метод сортировки, при котором каждый раз сливаются две самые длинные возможные подпоследовательности, называется естественным слиянием.

Упорядоченную подпоследовательность часто называют цепочкой. Но, поскольку слово цепочка чаще используется для обозначения последовательности символов, мы будем использовать слово серия, когда речь идет об упорядоченной подпоследовательности. Мы называем подпоследовательность а,-, .... ai, такую, что

ft < Oft+i для k = l...../ - 1

а, ,>сг, (2.25)

максимальной серией или, короче, серией. Итак, сортировка естественным слиянием сливает не последовательности фиксированной, заранее заданной длины, - а (максимальные) серии. Серии имеют то свойство, что при слиянии двух последовательностей, каждая из которых содержит п серий, воЗ' никает одна последовательность, содержащая ровно п серий. Таким образом, на каждом проходе общее число серий уменьшается вдвое, и число необходимых пересылок элементов в худшем случае равно п - [log2n], а в обычном случае даже меньше. Ожидаемое число сравнений, однако, намного больше, так как кроме сравнений, необходимых для упорядочения элементов, требуются еще сравнения соседних элементов каждого файла для определения концов серии.

Следующим нашим упражнением будет разработка алгоритма естественного слияния тем же поэтапным методом, который использовался при объяснении алгоритма простого слияния. Вместо массива он обрабатывает последовательный файл и представляет собой несбалансированную двухфазную трехленточную сортировку слиянием. Пусть исходная последовательность элементов задана в виде файла с, который конце работы должен содержать результат сортировки. (Разумеется, в реальных процессах обработки исходные дан-bie для сохранности сначала переписываются с ленты в ра-очнй файл с.) Используются две вспомогательные ленты а °- Каждый проход состоит из фазы распределения,- оторая Распределяет серии поровну из с в с и &, и фазы слияния



которая сливает серии из а и Ь в с. Этот процесс показд/ на рис. 2.13.


ь

фаза слияния фаза распределения


V Y у--

1-й проход 2-й проход и-й про од

Рис. 2.13. Фазы сортировки и проходы сортировки.

В качестве примера в табл. 2.11 показан файл с в исход, ном состоянии (строка I) и после каждого прохода (строки Таблица 2.11. Пример сортировки естественным слиянием

17 31 5 59 13 41 43 67 11 23 29 47 3 7 71 2 19 57 37 61

5 17 31 59 И 13 23 29 41 43 47 67 2 3 7 19 57 71 37 61

5 11 13 17 23 29 31 41 43 47 59 67 2 3 7 19 37 57 61 71

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 57 59 61 67 П,

2-4). В естественном слиянии участвуют 20 чисел. Заметим, что требуются только три прохода. Сортировка заканчивается, как только число серий в с будет равно 1. (Предполагается, что в исходном файле имеется хотя бы одна непустая серия.) Итак, пусть переменная / используется для подсчета числа серий, сливаемых в с. Если мы определим глобальные объекты

type tape = file of item; var c: tape

(2.26)

TO программу можно написать следующим образом: procedure natwalmerge; var /: integer; a,b: tape;

repeat rewrite(a); rewrite(b); resetic); distribute;

reset(a); reset{b); rewriteic); 1 := 0;.merge until 7 = 1

(2.271



ЧТО две фазы выражаются двумя отдельными опера-Теперь их надо уточнить, т. е. описать более по-( Р^** Подробные описания можно либо непосредственно ять в текст, либо представить в виде процедур, и тогда BcTjgHHO записанные операторы следует рассматривать ызовы процедур. На этот раз мы изберем последний gco6 и определим ......

procedure distribute, [из сваиb] begin

repeat copyrun( c,d); 2.28)

if -leof (c) tlien copyruii(c,b) until eo/(c)

procedure merge; begin [из a и b в c]

repeat mergeruii; I :- I+l

until eofib); 2.29)

if -eofia) then

hegin copyrun(a,c); I := 1+1 end

Предполагается, что при таком способе распределения в файлах а и b оказывается либо равное число серий, либо Ыя а содержит на одну серию больше, чем Ь. Поскольку -оответствующие пары серий сливаются, в файле а может казаться лишняя серия, которую следует просто переписать, фоцедуры merge и distribute формулируются с помощью одчиненных процедур mergerun и соругип, задачи которых .нтны. Теперь опишем эти процедуры более подробно; они ,Р%ют введения глобальной булевской переменной ear id of the run), значение которой показывает, достигнут ли Нец серии.

procedure соругип(уяг х,у: tape);

begin [перепись одной серии из X в у] (2.30)

repeat сору(х,у) until еог




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