logo
Сборная ответов к госэкзаменам

Листинг 1. Сортировка слиянием

procedure merge( k: integer; { длина входной серии } fl, f2, gl, g2: file of recordtype);

var outswitch: boolean; { равна true, если идет запись в gl и false, если в g2 }

winner: integer; { номер файла с меньшим ключом в текущей записи }

used: array[1..2] of integer; { used[j] сообщает, сколько записей прочитано к настоящему времени из текущей серии файла fj }

fin: array[1..2] of boolean; { fin[j]=true, если уже закончена серия из файла fj:

либо прочитано k записей, либо достигнут конец файла fj}

current: array[1..2] of recordtype; { текущие записи из двух файлов }

procedure getrecord ( i: integer); { Перемещение по файлу fi, не выходя за конец файла или

конец серии. Устанавливается fin[i]=true, если достигнут конец серии или файла }

begin

used[i]:= used[i] + 1;

if (used[i]= k) or(i = 1) and eof(fl) or (i = 2) and eof(f2) then

fin[i]:= true

else if i = 1 then read(fl, current[1])

else read(f2, current[2])

end; { getrecord }

begin { merge }

outswitch:= true; {первая объединенная серия записывается в gl}

rewrite(gl); rewrite(g2);

reset(fl); reset(f2);

while not eof(fl) or not eof(f2) do begin { слияние двух файлов } { инициализация }

used[l]:= 0,- used[2]:= 0;

fin[l]:= false; fin[2]:= false;

getrecord(l); getrecord(2);

while not fin[l] or not fin[2] do begin { слияние серий }

{ вычисление переменной winner (победитель) }

if fin[l] then winner:= 2 {f2 "побеждает" по умолчанию: серия из fl исчерпалась}

else if fin[2] then winner:= 1 {fl "побеждает" по умолчанию}

else {не исчерпалась ни одна из серий}

if current[1].key<current[2].key then winner:= 1

else winner:= 2;

if outswitch then write(gl, current[winner])

else write(g2, current[winner]); getrecord(winner)

end;

{ закончено слияние двух серий, далее надо "переключить" выходной файл и повторить процедуру }

outswitch:= not outswitch;

end

end; { merge }

Обратите внимание, что процедура merge, показанная в листинге 1, вовсе не требует, чтобы отдельная серия полностью находилась в памяти: она считывает и за­писывает последовательно запись за записью. Именно нежелание хранить целые се­рии в основной памяти заставляет нас использовать два входных файла. В противном случае можно было бы читать по две серии из одного файла одновременно.

Таблица 11.1. Сортировка слиянием

28 3

93 10

54 65

30 90

10 69

8

31 5

96 40

85 9

39 13

8 77

10

а) исходные файлы

28 31

93 96

54 85

30 39

8 10

8

3 6

10 40

9 65

13 90

69 77

22

б) серии длиной 2

3 5

28 31

9 54

65 85

8 10

69

10 40

93 96

13 30

39 90

8 10

22

в) серии длиной 4

3 5 10 28 31 40

93 96

8 8

10 10 22 69 77

9 13 30 39 54 65

85 90

г) серии длиной 8

359

10 13 28 30 31

39 40 54

65 85 90

8 8 10

10 22 69 77

д) серии длиной 16

3 5 8 8 9 10 10 10 13 22 28 30 31 39 40 54 65 69 77 85 90 93 96

е) серии длиной 32

Yandex.RTB R-A-252273-3
Yandex.RTB R-A-252273-4