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

Сортировка сбалансированным слиянием является наиболее простым методом сортировки, предполагающим многократное распределение и слияние серий.

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

Пусть исходный файл содержит 1700 записей. Допустим, что в оперативной памяти можно разместить не более 100 записей. Предположим также, что мы можем использовать для сортировки 4 файла, которые мы обозначим f1 f2 f3 f4. Исходным является файл f1. Будем использовать 2-путевое слияние. Начинаем сортировку. Считываем 100 записей, сортируем их одним из методов внутренней сортировки и записываем в файл f2. Затем считываем следующие 100 записей, сортируем и записываем в файл f3, следующие 100 сортированных записей снова записываем в файл f2 и т.д. В результате мы получим 9 серий по 100 записей в файле f3.

Далее серии файлов f2 и f3 сливаем и вновь в процессе слияния попеременно записываем, формируя новые серии, на файле f1 и f4. В итоге в файле f1 мы будем иметь 4 серии по 200 записей и 1 серию из 100 записей, а в файле f4 – 4 серии по 200 записей.

Аналогичный цикл слияний серий с f1 и f4 и записи на f2 и f3 приведёт к 2 сериям по 400 записей и 1 серии из 100 записей в f2 и к 2 сериям по 400 записей в f3.

После ещё трёх циклов в f1 окажется полностью отсортированный файл.

Процесс сортировки изображён на рисунке:

1(1700)

	F2		F3

8(100) 9(100)

4(200) 4(200) 1(100)

2(400) 1(100) 2(400)

Слияние:4 Распределение:4

1(800) 1(800)1(100)

				F3

1(1600) 1(100)

1(1700)

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

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

program balans;

const n=10;{количество записей в сериях при внутренней(начальной) сортировке и распределении}

type item=record

key:integer;

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

end;

filetype=file of item;

var f1,f2,f3,f4:filetype;

z,l,all:integer;

eor,per:boolean;

mas:array[1..n]of integer;

data:item;

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

{eor-индикатор конца серии}

procedure readfile;{процедура считывает 100 записей в массив mas}

begin

l:=0;

while not eof(f1)and not(l=n) do

begin l:=l+1;read(f1,data);mas[l]:=data.key;end;

all:=l;

end;

procedure massort;{процедура сортировки массива mas}

var buf,units:integer;

m:boolean;

begin

units:=all;

repeat

m:=true;;

units:=units-1;

for l:=1 to units do

begin

if mas[l]>mas[l+1]

then begin buf:=mas[l];mas[l]:=mas[l+1];mas[l+1]:=buf;m:=false;end;

end;

until m or (units=1);

end;

procedure sort(var x:filetype);{процедура считывает, сортирует а затем записывает на ленту серии по 100 записей}

begin

readfile;massort;

for l:=1 to all do begin data.key:=mas[l];write(x,data);end;

end;

procedure sortrun;{прцедура первоночальной (внутренней) сортировки и распределении}

begin

reset(f1);rewrite(f2);rewrite(f3);

while not eof(f1) do

{распределяем сначала на ленту f2 а затем на ленту f3 и т.д.}

begin sort(f2);if not eof(f1) then sort(f3);end;

close(f1);close(f2);close(f3);

end;

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 merge(var a,b,c:filetype);{процедура слияния серии}

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 ende(var a,b,c:filetype);

begin

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;

end;

procedure mer(var a,b,d,e:filetype);{процедура сливает серии из a и b и распределяет между d и e}

var con:boolean;

begin

con:=false;

reset(a);reset(b);rewrite(d);rewrite(e);

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

begin

merge(a,b,d);z:=z+1;con:=true;

if (not eof(a))and(not eof(b)) then begin merge(a,b,e);z:=z+1;con:=false;end;

end;

if con then ende(a,b,e);

ende(a,b,d);

close(a);close(b);close(d);close(e);

end;

begin

assign(f1,'c:\tp\file1');

assign(f2,'c:\tp\file2');

assign(f3,'c:\tp\file3');

assign(f4,'c:\tp\file4');

sortrun;

per:=false;

repeat

z:=0;

if per then begin mer(f1,f4,f2,f3);per:=false;end

else begin mer(f2,f3,f1,f4);per:=true;end;

until z=1;

end.

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

0 3 86 20 27 67 32 16 37 43 8 47 7 84 6 29 92 37 77 33 70 84 72 31 16 33 47 25 83 28 48 15 87 29 77 98 49 89 83 2 14 1 4 50 2 59 1 77 65 77 71 56 21 68 59 96 64 100 24 68 30 9 77 50 88 51 57 95 68 34 1 71 99 77 75 20 14 91 78 59 86 69 29 9 63 28 88 16 27 54 96 17 16 27 18 58 50 29 16 61 74 Нажмите Enter для продолжения!   0 1 1 2 2 3 6 7 8 9 9 14 14 14 15 16 16 16 16 16 17 18 20 20 21 24 25 27 27 27 28 28 29 29 29 29 30 31 32 33 33 34 37 37 43 47 47 48 49 50 50 50 51 54 56 57 58 59 59 59 61 63 64 65 67 68 68 68 69 70 71 71 72 74 75 77 77 77 77 77 77 78 83 83 84 84 86 86 87 88 88 89 91 92 95 96 96 98 99 100 Нажмите Enter для продолжения!

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

На втором этапе выполняется несколько циклов слияния этих серий во всё большие и большие серии, пока все записи не окажутся в одной серии.

Возможно ли при сортировке обойтись только тремя магнитными лентами?

Да, возможно. Для этого начальные серии распределяем на файлы Т2 и Т3 сливаем в файл Т1. Затем полученные серии снова распределяем по файлам Т2 и Т3, до тех пор, пока не получим в файле Т1 одну серию.

Недостатком такого метода является излишнее копирование, что увеличивает время сортировки.

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

Сколько требуется файлов для сбалансированного Р-путевого слияния?

В общем случае требуется 2Р файлов. Однако, если после распределения серий сливать их в один файл, то количество требуемых файлов сократится почти в два раза и будет равно Р+1, но за это приходится расплачиваться увеличением времени сортировки вдвое, за счёт дополнительного копирования, о чём уже говорилось.