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

ВЫХОДНЫМИ лентами. (В дальнейшем мы будем

просто лентой / .) Теперь в первом приблцл^ алгоритм можно записать следующим образом:

procedure tapemergesort; Yar tapeno;

I: integer; {числораспределяемых серий} . t: array [tapeno] of tapeno;

begin [распределение начальных серий HatH]...t [nh]} j := nh; I := 0;

repeat if у < nh then / := /+1 else / := Ij

перепись одного отрезка cfO на ленту j} ; I := /+1

until eof(fO);

for г := 1 to n do t[il := i;

repeat [слияние U3t[l]...t [nh] в t [nh + 1] ... Г [n]}

установка входных лент ;

У := nh+1; [j-индекс выходной ленты] repeat / := /+1;

слияние серии а с входных лент на t [/] if У < п then у := у+1 else j := иА+1 until все входные ленты исчерпаны j переключение ленты until / = 1; -

[отсортированный файл находится.на ленте t Щ]

Прежде всего уточним операцию копирования, котор используется при начальном распределении серий; вновь дем вспомогательную переменную для буферизации пос1 него считанного элемента

buf: item

и заменим перепись одного отрезка с /О на ленту / onef тором

repeat read(fO, buf);

write[f[j], buf) (22

until (bufkey > fOt.key) V eof(fO)

Перепись серии заканчивается, либо когда встреча^, первый элемент следующей серии {buf.key >fOf.key), когда достигается конец всего входного файла (eof(fO))-

Теперь в алгоритме сортировки остались операторы

установка входных лент; 1) LgflHHe серии с входных лент на ленту t[j]; з| переключение ленты

р предикат

все входные ленты исчерпаны,

оторые нужно определить более подробно. Во-первых, мы полжны аккуратно вести учет текущих входных файлов. Заметим, что количество активных входных файлов может быть меньще чем N/2. Действительно, максимальное число входных файлов может быть равно числу серий; сортировка заканчивается в том случае, когда остается только один файл. Причем может оказаться, что количество серий в начале последнего прохода сортировк и меньше чем nh. Поэтому мы вводим переменную kl для обозначения числа текущих входных файлов. Инициацию kl мы включим в оператор (1) следующим образом:

if I < nh then kl := I else kl := nh; for I := 1 to Arl do reset(jy[i]]);

Понятно, что оператор (2) должен уменьшать значение kl, как только исчерпывается какой-либо входной файл. Следовательно, предикат (4) легко можно выразить отношением

kl = 0

Оператор (2) уточнить труднее; он содержит циклический выбор наименьшего ключа из текущих входных данных; выбранный таким образом элемент посылается в выходной файл, т. е. на текущую выходную ленту. Этот процесс осложняется еще тем, что нужно искать конец каждой серии. Конец серии считается достигнутым, если (1) очередной ключ Меньше текущего, или (2) достигнут конец входного файла. последнем случае лента исключается из работы путем уменьшения kl, в первом случае отрезок закрывается, т. е. файл перестает участвовать в дальнеймем выборе элементов. Но только до тех пор, пока не окончится формирование теку-Чсй выходной серии. Отсюда ясно, что необходима вторая Неременная k2 для обозначения числа входных лент, которые Текущий момент используются для выбора следующего Демента. Это значение вначале полагается равным 1 Уменьшается, когда какая-либо серия закрывается по ус- овию (1).

К сожалению, недостаточно ввести переменную k2: мало ать число лент -нужно знать точно, какие именно ленты

]ogram halancedmerge (output};

{сбшмнсировднная п^путвая сортировка слиянием)

const 6; й = 3; {число лент]

type item ~ record

key: integer ,

end ; tape = &eo{item; tapeno - 1.. и;

y t leng, rand: integer; [используются для формирования:фа{(, eot: boolean; [конец ленты]

buf: item;

/0: tape; {/0 - входная Лента со случайными числами]

/: array [1.. и] of tape; procedure/w((var/: tape; и: tapeno};

var z: integer; 16epi wiMkCTAPEV йГГ); zT-D]--

while -leof(f) do

begin г й4/, iu/); write(output, bif.key: S); z := г+lj i

if z = 25 then I

begui writeh(outpui); г := 0} end

end ; i

if z .t 0 (hen vmteh (output); reset(f) end {list} ;

procedure tapemergesort; var i,j,mx,tx: tapeno; kl,k2,l; integer; X, min: integer; t, ta: яаяу [tapeno] ot tapeno; begin [распределение начальных серий иа t[l}... tlnh]] for ? := 1 to nh do rewrite(f[i]}; J:= nh; l:= 0;

repeat if j < nh then j :== j+1 else у ;= 1; {перепись одной серии cfO яа ленту]] fWl+l;

repeat rearf(/0, buf); write(f[J], buf) until (риГ.кеу > fO\ .key) V eof(fO) until eo/(/0);

for i:= 1 to n do /[/] := /; repeat {слияние с t[V\... tinh] на tlnh + 1]... i[ri]] itKnh then /cl :== / else M := ий, {кХЧМСЛО входных лент на этой фазе] forItoMdo

begin гезеЦЛ.ФШ Ш[Ш ФЪ; := Ш end ;