Файл: 2. Лекции Паскаль (Часть 2).doc

Как было показано выше, простым слиянием состоит из двух фаз: фазы разделения серий по двум файлам и фазы слияния упорядоченных серий. В соответствии с этим напишем две процедуры: разделения и слияния.

Исходные данные представим следующим образом.

type item=record

key:integer;

{описание других полей}

end;

filetype=file of item;

var a,b,c:filetype;

l:integer;

Исходные данные разместим в файле С, в него же будем записывать результаты слияний серий. В файл А и В будем распределять серии из файла С.

Пусть М-длина серии (М=1,2,4,8,……). Тогда распределение серий длиною М по файлам А и В можно выполнить следующим образом:

begin

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

repeat

{переписать очередную серию из файла С в файл А}

{переписать следующую серию из файла С в файл В}

until eof(c);

close(a);close(b);close(c);

end;

Посмотрим как можно переписать серию. Для этого необходимо последовательно переписывать записи до тех пор, пока не кончится либо серия, либо файл С. Поскольку серии имеют фиксированную длину, определить конец серии не представляет труда, для этого достаточно организовать счётчик. Тогда переписать серию из файла С в А можно следующим образом.

k:=0; {счётчик}

ok:=eof(c);

while not ok do

begin

read(c,buf);write(a,buf);

k:=k+1;

ok:=eof(c) or (k=l);

end;

Аналогично переписывается серия из С в В. запишем окончательно процедуру распределения серий из С в А и В.

{процедура распределения серий}

procedure Distribute;

var buf:item;

k:integer;

ok:boolean;

begin

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

repeat

k:=0;ok:=eof(c);

while not ok do

begin

read(c,buf);write(a,buf);

k:=k+1;ok:=eof(c) or (k=l);

end;

k:=0;ok:=eof(c);

while not ok do

begin

read(c,buf);write(b,buf);

k:=k+1;ok:=eof(c) or (k=l);

end;

until eof(c);

close(a);close(b);close(c);

end;

Теперь рассмотрим процедуру слияния серий фиксированной длины М из файлов А и В в файл С. Вспомним алгоритм слияния. Читаем начальные элементы очередной серии из файлов А и В, сравниваем их и записываем не больший элемент в С, а на его место читаем следующий элемент из соответствующего файла. И так до тех пор, пока не закончится серия в каком-нибудь из файлов.

Попробуем записать алгоритм следующим образом:

read(a,bufa);read(bufb);k1:=0;k2:=0;

while (k1<l) and (k2<l) do {повторять, пока не закончится серия}

if bufa.key<bufb.key

then

begin;write(c,bufa);read(a,bufa);k1:=k1+1;end

else

begin;write(c,bufb);read(b,bufb);k2:=k2+1;end

Если внимательно проанализировать записанный выше алгоритм, можно увидеть следующие ошибки.

Во первых, когда записывается в файл С последний элемент серии (К1 или К2 равны М), не надо читать следующий элемент файла, т.к. он относится уже к другой серии.

Во вторых, мы не учитываем то обстоятельство, что последняя серия в файле может содержать элементов меньше, чем М. Поэтому, необходимо обрабатывать не только конец серии, но и конец файла.

В третьих, когда мы записываем в файл С последний элемент очередной серии, например, из файла А, в буфер файла В (bufb) остаётся элемент, который необходимо переписать в файл С.

С учётом вышесказанного, алгоритм запишем следующим образом:

ok:=eof(a) or eof(b);

if not ok

then

begin;read(a,bufa);read(b,bufb);end;

k1:=0;k2:=0;

while not ok do {повторять, пока не закончится}

begin

if bufa.key<bufb.key

then

begin

write(c,bufa);

k1:=k1+1;

ok:=(k1=l)or eof(a);

if not ok then read(a,bufa)

else begin

write(c,bufb);

k2:=k2+1;

end;

end

else

begin

write(c,bufb);

k2:=k2+1;

ok:=(k2=l)or eof(b);

if not ok then read(b,bufb)

else begin

write(c,bufa);

k1:=k1+1;

end;

end;

end;

После того, как полностью переписана серия какого-либо файла, необходимо переписать в файл С остаток серии из другого файла.

переписать остаток серии файла А}

while (k1<l) and not eof(a) do

begin

read(a,bufa);write(c,bufa);k1:=k1+1;

end;

{переписать остаток серии файла В}

while (k2<l) and not eof(b) do

begin

read(b,bufb);write(c,bufb);k2:=k2+1;

end;

Окончательно процедура слияния серий длиною М из файла А и В в файл С будем иметь следующий вед.

{процедура слияния серий длиной М}

procedure Merge;

var bufa,bufb:item;

k1,k2:integer;

ok:boolean;

begin

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

repeat {повторять, пока не закончатся оба файла А и В}

z:=z+1; {подсчитываем число полученных серий}

ok:=eof(a) or eof(b);

if not ok then begin;read(a,bufa);read(b,bufb);end;

k1:=0;k2:=0;

while not ok do {повторять, пока не закончится серия или файл}

begin

if bufa.key<bufb.key

then

begin

write(c,bufa);

k1:=k1+1;

ok:=(k1=l)or eof(a);

if not ok then read(a,bufa)

else begin

write(c,bufb);

k2:=k2+1;

end;

end

else

begin

write(c,bufb);

k2:=k2+1;

ok:=(k2=l)or eof(b);

if not ok then read(b,bufb)

else begin

write(c,bufa);

k1:=k1+1;

end;

end;

end;

{переписать остаток серии файла А}

while (k1<l) and not eof(a) do

begin

read(a,bufa);write(c,bufa);k1:=k1+1;

end;

{переписать остаток серии файла В}

while (k2<l) and not eof(b) do

begin

read(b,bufb);write(c,bufb);k2:=k2+1;

end;

until eof(a) and eof(b);

close(a);close(b);close(c);

end;

Здесь Z-глобальная переменная, которая необходима для определения конца процесса сортировки. Сортировка заканчивается, когда на очередном проходе мы получим одну серию (Z=1).

Теперь мы можем написать программу внешней сортировки методом простого слияния.

Программа использует уже готовый файл содержащий не отсортированные данные и не распечатывает отсортированный файл (программа только сортирует файл file1).

programma primemerge;

type item=record

key:integer;

{описание других полей}

end;

filetype=file of item;

var a,b,c:filetype;

l,z:integer;

procedure Distribute;

var buf:item;

k:integer;

ok:boolean;

begin

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

repeat

k:=0;ok:=eof(c);

while not ok do

begin

read(c,buf);write(a,buf);

k:=k+1;ok:=eof(c) or (k=l);

end;

k:=0;ok:=eof(c);

while not ok do

begin

read(c,buf);write(b,buf);

k:=k+1;ok:=eof(c) or (k=l);

end;

until eof(c);

close(a);close(b);close(c);

end; {distribute}

procedure Merge;

var bufa,bufb:item;

k1,k2:integer;

ok:boolean;

begin

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

repeat {повторять, пока не закончатся оба файла А и В}

z:=z+1; {подсчитываем число полученных серий}

ok:=eof(a) or eof(b);

if not ok then begin;read(a,bufa);read(b,bufb);end;

k1:=0;k2:=0;

while not ok do {повторять, пока не закончится серия или файл}

begin

if bufa.key<bufb.key

then

begin

write(c,bufa);

k1:=k1+1;

ok:=(k1=l)or eof(a);

if not ok then read(a,bufa)

else begin

write(c,bufb);

k2:=k2+1;

end;

end

else

begin

write(c,bufb);

k2:=k2+1;

ok:=(k2=l)or eof(b);

if not ok then read(b,bufb)

else begin

write(c,bufa);

k1:=k1+1;

end;

end;

end;

{переписать остаток серии файла А}

while (k1<l) and not eof(a) do

begin

read(a,bufa);write(c,bufa);k1:=k1+1;

end;

{переписать остаток серии файла В}

while (k2<l) and not eof(b) do

begin

read(b,bufb);write(c,bufb);k2:=k2+1;

end;

until eof(a) and eof(b);

close(a);close(b);close(c);

end; {merge}

begin {main}

assign(a,'{имя внешнего файла}');

assign(b,'{имя внешнего файла}');

assign(c,'{имя внешнего файла}');

l:=1;

repeat {повторять, пока не получим одну серию}

distribute;z:=0;

merge;l:=(2*l);

until z=1;

end.

Результат работы:

В качестве примера в таблице показан файл С в исходном состояние и после каждого прохода. В таблице показаны только значения ключей, причём серии разделены апострофом.

Заметим, что требуется четыре прохода.

Пример сортировки простым слиянием.

Исходный файл

С: 44 55 12 42 94 18 06 67 15 17 14 15 19 07

Первый проход (М=1)

А: 44 12 94 06 15 14 19

В: 55 42 18 67 17 15 07

С: 44 55 12 42 18 94 06 67 15 17 14 15 07 19

Второй проход (М=2)

А: 44 55 18 94 15 17 07 19

В: 12 42 06 67 14 15

С: 12 42 44 55 06 18 67 94 14 15 15 17 07 19

Третий проход (М=4)

А: 12 42 44 55 14 15 15 17

В: 06 18 67 94 07 19

С: 06 12 18 42 44 55 67 94 07 14 15 15 17 19

Четвёртый проход (М=8)

А: 06 12 18 42 44 55 67 94

В: 07 14 15 15 17 19

С: 06 07 12 14 15 15 17 18 19 42 44 55 67 94

Более совершенным методом сбалансированного слияния является сортировка естественным слиянием.

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

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

Следующим нашим упражнением будет разработка алгоритма естественного слияния методом структурного программирования «сверху-вниз».

Запишем программу следующим образом:

program naturalmerge;

type item=record

key:integer;

{описание других полей}

end;

filetype=file of item;

var a,b,c:filetype;

z:integer; {для подсчёта числа серий}

eor:boolean;{индикатор конца серии}

begin

assign(a,'{имя внешнего файла}');

assign(b,'{имя внешнего файла}');

assign(c,'{имя внешнего файла}');

repeat

distribute;z:=0;

merge;

until z=1;

end.

Здесь две фазы сортировки (разделения и слияния) реализуются отдельными процедурами: Distribute и Merge. Запишем эти процедуры.

{процедура распределения серий}

procedure distribute; {из С в А и В}

begin

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

repeat

copyrun(c,a);

if not eof(c) then copyrun(c,b);

until eof(c);

close(a);close(b);close(c);

end;

{процедура слияния серий}

procedure merge;

begin

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

while (not eof(a))and(not eof(b)) do

begin

mergerun;z:=z+1;

end;

while not eof(a) do begin;copyrun(a,c);z:=z+1;end;

while not eof(b) do begin;copyrun(b,c);z:=z+1;end;

close(a);close(b);close(c);

end;

Здесь Copyrun(x,y)-процедура копирования серий из файла Х в файл Y, а Mergerun-процедура слияния двух серий из файлов A и B в файл C. Опишем эти процедуры. Будем использовать булевскую переменную eor, значение которой показывает, достигнут ли конец серии. Введём также процедуру Copy(x,y), которая копирует очередную запись их файла X в файл Y и определяет, достигнут ли конец серии.

{процедура копирования серий}

procedure copyrun(var x,y:filetype);

{переписать серии из X в Y}

begin

repeat

copy(x,y);

until eor;

end;

При реализации процедуры Copy надо находить конец серии. Для этого нужно сравнить ключ последней переписанной записи с ключом следующей. То есть мы должны видеть следующую запись. Это «заглядывание вперёд» достигается использованием буферной переменной файла X^. Однако, не все реализации языка Паскаль поддерживает буферную переменную. В частности буферные переменные отсутствуют в Турбо Паскаль. В этом случае наиболее просто задача решается, если использовать прямой доступ к файлу, который реализуется в Турбо Паскале. Так это и сделано в процедуре Copy.

{процедура копирования записи и определения конца серии}

procedure copy(var x,y:filetype);

var buf,buf1:item;

begin

read(x,buf):write(y,buf);

if eof(x) then eor:=true

else begin

{заглядываем вперёд}

read(x,buf1);

{возвращаемся на исходную запись}

seek(x,filepos(x)-1);

eor:=buf1.key<buf.key

end;

end;

Здесь seek-процедура, которая устанавливает указатель файла на требуемую компаненту, filepos-функция, возвращающая номер текущей компоненты файла.

Теперь запишем процедуру Mergerun. Здесь мы также будем использовать процедуру seek для того, чтобы указатель файла всегда находился на записях, которые сравниваются. Процесс сравнения и выбора по ключу при слиянии серий завершается, как только будет исчерпана одна из двух серий. После этого остаток другой серии нужно скопировать в выходной файл С. это осуществляется вызовом процедуры Copyrun.

{процедура слияния двух серий}

procedure mergerun;

{слияние серий из А и В в С}

var bufa,bufb:item;

begin

repeat

read(a,bufa);seek(a,filepos(a)-1);

read(b,bufb);seek(b,filepos(b)-1);

if bufa.key<bufb.key

then begin;copy(a,c);if eor then copyrun(b,c);end

else begin;copy(b,c);if eor then copyrun(a,c);end;

until eor

end;

В качестве примера в таблице показан файл С в исходном состоянии и после каждого прохода. Также как и в предыдущем примере серии в таблице разделены. Заметим, что здесь для сортировки требуется только 3 прохода.

Пример сортировки естественным слиянием

Исходный файл

С: 44 55 12 42 94 18 06 67 15 17 14 15 19 07

Первый проход

А: 44 55 18 15 17 07

В: 12 42 94 06 67 14 15 19

С: 12 42 55 94 06 18 67 14 15 15 17 19 07

Второй проход

А: 12 42 44 55 94 14 15 15 17 19

В: 06 18 67 07

С: 06 12 18 42 44 55 67 94 07 14 15 15 17 19

Третий проход

А: 06 12 18 42 44 55 67 94

В: 07 14 15 15 17 19

С: 06 07 12 14 15 15 17 18 19 42 44 55 67 94

В заключении заметим, что хотя и предполагается, что процедура Distribute посылает серии поровну в оба файла, действительное количество выходных серий в «а» и «b» могут различаться больше чем на 1. Например, рассмотрим также исходные данные

С: 08 06 09 11 09 13 15 05 07 20 19 27 31 13 25 (6 серий)

После разделения получим

А: 08 09 13 15 19 27 31 (1 серия)

В: 06 09 11 05 07 20 13 25 (3 серии)

Этот пример показывает, что простое распределение серий в несколько файлов может дать в результате меньшее число выходных серий, чем входных. Это происходит потому, что первый элемент (i+1)-й серии может быть больше, чем последний элемент i-й серии, что приведёт к автоматическому слиянию двух серий в одну, что и наблюдается в примере при распределении серий в файл А. Это следует учитывать при последующем слиянии серий, а именно, после достижения конца одного из файлов копировать весь остаток другого файла, а не только одну серию. Именно та и написана процедура Merge.

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

Программа использует уже готовый файл содержащий не отсортированные данные и не распечатывает отсортированный файл (программа только сортирует файл file1).

program naturalmerge;

type item=record

key:integer;

{описание других полей}

end;

filetype=file of item;

var a,b,c:filetype;

z:integer; {для подсчёта числа серий}

eor:boolean; {индикатор конца серии}

procedure copy(var x,y:filetype);

var buf,buf1:item;

begin

read(x,buf):write(y,buf);

if eof(x) then eor:=true

else begin

{заглядываем вперёд}

read(x,buf1);

{возвращаемся на исходную запись}

seek(x,filepos(x)-1);

eor:=buf1.key<buf.key

end;

end;

procedure copyrun(var x,y:filetype);

{переписать серии из X в Y}

begin

repeat

copy(x,y);

until eor;

end;

procedure mergerun;

{слияние серий из А и В в С}

var bufa,bufb:item;

begin

repeat

read(a,bufa);seek(a,filepos(a)-1);

read(b,bufb);seek(b,filepos(b)-1);

if bufa.key<bufb.key

then begin;copy(a,c);if eor then copyrun(b,c);end

else begin;copy(b,c);if eor then copyrun(a,c);end;

until eor

end;

procedure distribute; {из С в А и В}

begin

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

repeat

copyrun(c,a);

if not eof(c) then copyrun(c,b);

until eof(c);

close(a);close(b);close(c);

end;

procedure merge;

begin

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

while (not eof(a))and(not eof(b)) do

begin

mergerun;z:=z+1;

end;

while not eof(a) do begin;copyrun(a,c);z:=z+1;end;

while not eof(b) do begin;copyrun(b,c);z:=z+1;end;

close(a);close(b);close(c);

end;

begin {main}

assign(a,'{имя внешнего файла}');

assign(b,'{имя внешнего файла}');

assign(c,'{имя внешнего файла}');

repeat

distribute;z:=0;

merge;

until z=1;

end.

Результат работы: