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

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

if еог then соругт (а,с) end until еог

procedure merge , begin [из a и be с} . while -\eof{a) Л -ieof(b) do

iKg\n mergerun; I l+l

end;

while-еоДа) do

begin copyrun {a,c); 1 /Ы end;

while -neof(b) do begin copyrun (b,c); I:~ l+l end ; list (c) end ; begin

repeat rewrite(a); rewrite(b); reset(c); distribute;

reset {a); reset(b); rewrite(c); / := 0; merge; until / = 1 end ;

begin [основная программа; чтение входной последовательности с О в конце) rewrite(c); read(buf.key); repeat write(c.buf); read(buf.key) until .key = 0: fo/(c); naturalmerge 1 fo/(c)

end .

Программа 2.14. Сортировка естественным слиянием.

енив процедуру слияния, а не процедуру распределения.

орая изначально является ошибочной, то значит, что схему распределения мы оставляем нетро-

яой, а отказываемся от требования, чтобы серии распре-ялись поровну на две ленты. В результате программа

.Кет работать неоптимальным образом. Однако в худшем

Рйанте она сохраняет те же характеристики; кроме того.



122 2. Сортировка

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

тивности не являются серьезным аргументом против д^ рещения.

Если требование о распределении серий поровну J нено , то процедуру слияния следует изменить таким образе чтобы после достижения конца одного из файлов копировал'! весь остаток другого файла, а не только одна серия.

Это - несложное изменение, оно намного проще, ц^, какое-либо изменение схемы распределения. (Мы предлагав читателю самому убедиться в правоте этого утверждении! Пересмотренная версия алгоритма слияния включена в OKoi чательную программу 2.14.

2.3.3. Сбалансированное многопутевое слияние

Затраты на последовательную сортировку пропорцц нальны числу проходов, так как по определению на каждс проходе происходит перепись всего множества данных. Од из способов уменьшить это число - распределять серии ь более чем две ленты. Слияние г серий, которые поров! распределены на лентах, дает в результате последовате! ность из r/N серий. Второй проход уменьшает это чио до r/N, а третий-до r/N, и после k проходов остает; r/N отрезков. Итак, общее число проходов при сортировке элементов N-путевым слиянием k = [logw п]. Поскольку i каждом проходе производится п операций переписи, общ число операций переписи в худшем случае будет

M = n-[\og!jn].

В качестве следующего упражнения мы построим пр; грамму сортировки, основанной на многопутевом слиянй Чтобы подчеркнуть различие между этой программой и ош санной выше процедурой естественного двухфазного слияни! мы определим многопутевое слияние как однофазную сбала! сированную сортировку слиянием. Это означает, что каждом проходе имеется равное число входных и выходи файлов, в которые поочередно распределяются следуюШ' одна за другой серии. При использовании файлов aiif ритм будет основан на Л^/2-путевом слиянии, если счита что N четно. Следуя принятой ранее стратегии, мы не буД^ заботиться о том, чтобы предотвратить автоматическое сЛ* ние двух Соседних серий, попавших на одну ленту. СлеД тельно, нам приходится разрабатывать программу слйя1; без требования, чтобы на входных лентах содержалось стр* одинаковое число серий.



э'гой программе мы впервые встречаем естественное п зование структуры данных, представляющей собой ici файлов. В самом деле, удивительно, насколько велико т этой программы от предыдущей в результате пере- д от двухпутевого к многопутевому слиянию. Это проис-\г прежде всего потому, что теперь процесс слияния не

йожет

просто завершаться после того, как будет исчерпан из входных файлов. Вместо этого нужно вести список однйх файлов, которые пока активны, т. е. не исчерпаны. rtLvroe усложнение возникает из-за необходимости переключать группы входных и выходных лент после каждого

вначале, в дополнение к двум знакомым нам типам item а tape, определим тип номера ленты:

tapeno=-l..N (2.33)

Очевидно, что номера лент нужны, для того чтобы индексировать массив файлов. Будем считать, что исходная последовательность элементов задана переменной

fO: tape (2.34)

и для сортировки мы имеем в распоряжении N лент, где W четно:

f:array[tapeno] of tape (2.35)

Для решения проблемы переключения лент рекомендуется использовать карту ленточных индексов. Вместо того чтобы обращаться к ленте непосредственно с помощью индекса /, к ней адресуются через карту t, т. е. вместо

f[i] мы пишем f [[/]],

где карта определена как

t:arrdy[tapeno]oftapeno - (2.36)

Если первоначально t [i] = i для любого /, то переключение Роизводится просто при помощи обмена пар компонент

карты

t[\]t[nh+\\ f[2j-.->/[nA + 2]

t[nh\<t[n\,

is nh = n/2. Следовательно, мы всегда можем считать

f\m].....f{t{nh\\

j Дными лентами, а

./[/[пЛ-Ы]].....f[i{n\\




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