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

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

ffor i := 1 fow-I do begin dlfl z + - a[i\; a\i] := г + a[i+l]

end end ;

end ;

fad

procedure copyrun; . tegin [перепись одной серии с/О на ленту jy

repeat read(fО, ЬиГ); write(J-[j], buf);

шйЙ€о/(/0) V {buf .key > fO\ .key);

Iast[j\ := buf .key end;

leffA [распределение.начальныхсерий] for J := i ton-I do

begin йИ := 1; d[q :== 1: .rewn7e(/H) end ;

level := 1;; := 1; a[n] := 0; ф] 0; repeat selecttape; copyrun until eo/(/0) V (У=и-1); while ~>eof{f) do begm selecttape;

ttlast[j] /Ot .fcejthen

begin [продолжение прежней серии] copyrun;

ifeof(fO) then rffjl d[J] + t else co/ynvw

else copyrun end ;

for i := 1 to И-1 do reset(J[i\); for I := 1 towdol := i; repeat [слияние с til] ... tin ~ I] на t[n]X 2 := a[n-l]; din] := 0; rewrite{f[t[riS); xepeat к := 0; [слияние одной серии] for / 1 ton-1 do И ф] > 0 then d[i] := d[ii-l else begin k:== k+l; ta[k] t[i] end ;

if fe = 0 then Ф1 := d[n] + 1 else

begin [слияние одного действительного отрезка

с tin... am



repeat / := 1; тх := 1; min ЯЫЩ .key; while i < к йо

begin /х /[to[/]]t .key; if д; < min then begin min := x; mx := i end

end ; I

{ta\mx] содержит наименьший элемент, пересьщц его на i{n\)

readif[tdimx]\, buf); eot eofif[ta[mx]\); writejfim, buf);

if {buf .key > y[ta[mx\\].key) V eot then begin {сброс этой ленты ] ta[mx] := talk]; к := k-1

nntil fc x= 0 end ; z :- z-1 until г = 0;

reset(Atln]]); list(flt[nji, .{переключение ленты) tn := An]; dn := Ф]; z := [ -!]; for i := n downto 2 do

begin 4] := аЩ := г

end ; . i[l]:== tn;d[l]:= dn;a[l]:z; {отсортированный файл находится на til]] listMi]], tiny, level := level - 1 until level ==0; end [polyphasesort] ;

begin [формирование случайного файла] leng t= .200; rand := 7789; repeat rand (131071*r <?) mod 2147483647}

buf .key := rantf div 2147484; WriteifO, buf); leng := /e g- - 1 until leng = 0;

wK/o); M/o, 1);

polyphasesort

Программа 2.16. Многофазная сортировка.



2.3.5 Распределение начальных серий

Мы пришли к сложным программам последовательной сортировки, поскольку более простые методы, работающие с массивами, требуют наличия достаточно большой памяти с произвольным доступом, чтобы хранить все сортируемое множество данных. Очень часто такой памяти нет, вместо нее приходится использовать достаточно вместительные запоминающие устройства с последовательным доступом. Мы ви-дим^ что методы последовательной сортировки, рассмотренные выше, не требуют практически никакой оперативной памяти, кроме буферов для файлов и, разумеется, самой программы. Но в действительности даже небольшие вычислительные машины обладают некоторой оперативной памятью с произвольным доступом, которая почти всегда больше той, которая требуется для разработанных здесь программ. Непростительно было бы не попытаться использовать ее оптимальным образом.

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

Конечно, мы сразу обращаемся к логарифмическим методам сортировки массивов. Наиболее подходящий из них - то сортировка с помощью дерева, или пирамидальная сортировка (см. разд. 2.2.5). Пирамиду можно рассматривать туннель, через который должны пройти все компоненты Фэйла, некоторые - быстрее, некоторые - медленнее. Наименьший ключ легко извлекается с вершины пирамиды, а его Замещение - очень эффективный процесс. Пропуск компо-Иты с входной ленты /О через весь пирамидальный тун-

зцица заключается в том, что алгоритм исключения ленты сколько проще. Как производится поворот карты ленточ- х индексов и соответствующих счетчиков dt (и перевычис-пение коэффициентов ai при переходе на низший уровень) - Очевидно, это можно подробно видеть в программе 2.16, ко-ррая полностью описывает алгоритм многофазной сортировки




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