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

⇐ ПредыдущаяСтр 12 из 17Следующая ⇒

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

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

Пусть исходный файл содержит 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)

8(100) 9(100)

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

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

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

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

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;

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, но за это приходится расплачиваться увеличением времени сортировки вдвое, за счёт дополнительного копирования, о чём уже говорилось.

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

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

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

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

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;

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

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

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;

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

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).

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

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;

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

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.

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

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

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

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

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

С: 44551242941806671517 14 151907

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

А: 44129406151419

В: 55421867 1715 07

С: 44 5512 4218 9406 6715 1714 1507 19

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

А: 44 5518 9415 1707 19

В: 12 4206 6714 15

С: 12 42 44 5506 18 67 9414 15 15 1707 19

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

А: 12 42 44 5514 15 15 17

В: 06 18 67 9407 19

С: 06 12 18 42 44 55 67 9407 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

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

⇐ Предыдущая 7 8 9 10 111213 14 15 16 Следующая ⇒