Зауважимо, що в наведеному алгоритмі сортування злиттям копіювання масиву в допоміжний указано лише для того, щоб ідею алгоритму було простіше сприйняти. Цей алгоритм нескладно переробити так, щоб замість копіювання в додатковий масив відбувалося злиття в нього упорядкованих ділянок. Отже, на кроках з номерами 1, 3, 5, … має відбуватися злиття в допоміжний масив, а на кроках 2, 4, 6, … - злиття в протилежному напрямку.

Завершуючи описання сортування злиттям, скажемо, що цей алгоритм є першим із ефективних алгоритмів сортування. У 1945 році його винайшов Джон фон Нейман, один із піонерів програмування.

Серйозним недоліком цього алгоритму є необхідність додаткового масиву такої ж довжини, як і в основного.

Реалізація завдань алгоритмом злиття на мові програмування Turbo Pascal. Нехай, маємо два впорядкованих масиви цілих значень, використовуючи метод злиття сформувати впорядкований по зростанню масив, що містить всі елементи даних масивів.

Program Zluttja;

uses crt;

const p=7; a=6;

var c:array[1..p] of real;

d:array[1..a] of real;

f:array[1..p+a] of real;

i,j,n:integer;

begin

clrscr;

writeln('vvedit pershy poslidovnist, kogen nastupnui bilshui poperednogo');

for i:=1 to p do readln(c[i]);

writeln('vvedit drygy poslidovnist, kogen nastupnui bilshui poperednogo');

for i:=1 to a do readln(d[i]);

clrscr;

writeln('-------------poslidovnist C-----------');

writeln('kilist elementiv = ', p);

for i:=1 to p do write(c[i]:4:2,' ');

writeln;

writeln('-------------poslidovnist D-----------');

writeln('kilist elementiv = ', a);

for i:=1 to a do write(d[i]:4:2,' ');

i:=1; j:=1; n:=0;

while (i<=p) and (j<=a) do

begin

inc(n);

if c[i]>d[j] then begin

f[n]:=d[j];

inc(j);

end

else begin

f[n]:=c[i];

inc(i);

end;

end;

while i<=p do

begin

inc(n); f[n]:=c[i]; inc(i);

end;

while j<=a do

begin

inc(n); f[n]:=d[j]; inc(j);

end;

writeln;

writeln('-------------------Sformovanui masuv-----------');

for i:=1 to p+a do write(f[i]:4:2,' ');

readln;

end.

2. Природне злиття

При використанні методу прямого злиття не приймається в увагу те, що вихідний файл може бути лише частково відсортованим, тобто містити впорядковані підпослідовності записів. Серією називається підпослідовність записів ai, a(i+1),..., aj така, що ak <= a(k+1) для всіх i <= k < j, ai < a(i-1) і aj > a(j+1). Метод злиття впорядкованих серій ґрунтується на розпізнаванні серій при розподілі і їхньому використанні при наступному злитті.

Як і у випадку прямого злиття, сортування виконується за кілька кроків, у кожному з яких спочатку виконується розподіл файлу A по файлах B і C, а потім злиття B і C у файл A. При розподілі розпізнається перша серія записів і записується у файл B, друга - у файл C і т.д. При злитті перша серія записів файлу B зливається з першою серією файлу C, друга серія B із другою серією C і т.д. Якщо перегляд одного файлу закінчується раніше, ніж перегляд іншого (через різне число серій), те залишок недопереглянутого файлу цілком копіюється в кінець файлу A. Процес завершується, коли у файлі A залишається тільки одна серія. Приклад сортування файлу показаний на малюнках 1 та 2.

36

Рис. 1. Перший крок

36

Рис. 2. Другий крок

Очевидно, що число читань/перезаписів файлів при використанні цього методу буде не гірше, ніж при застосуванні методу прямого злиття, а в середньому - краще. З іншого боку, збільшується число порівнянь за рахунок тих, які потрібні для розпізнавання кінців серій. Крім того, оскільки довжина серій може бути довільної, то максимальний розмір файлів B і C може бути близький до розміру файлу A.

Реалізація методу мові програмування Turbo Pascal. Нехай маємо типізований файл додатних цілочисельних даних, використовуючи метод злиття впорядкованих серій (природне злиття) відсортувати цей файл по зростанню.

Примітка: Для генерування початкового файлу тут і надалі в курсовій програмі використовується файл Generat.pas, що формує бінарні файли. Лістінг даної програми поданий в додатках.

Program Natural_sort;

type Item=record

key:longint;

end;

TFile=file of Item;

var

f0:TFile;

procedure merge(k:integer;var f1,f2,g1,g2:TFile);

var outSwitch:boolean;

Winner:integer;

Used:array[1..2] of integer;

Fin:array[1..2]of boolean;

current:array[1..2]of Item;

procedure GetItem(i:integer);

begin

if(Used[i]=k)or((i=1)and eof(f1))or((i=2)and eof(f2)) then Fin[i]:=True

else if i=1 then read(f1,Current[1])

else read(f2,Current[2]);

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

end;

begin

OutSwitch:=true;

rewrite(g1);rewrite(g2);

reset(f1);reset(f2);

while (not eof(f1)) or (not eof(f2)) do

begin

Used[1]:=0;Used[2]:=0;

Fin[1]:=false;Fin[2]:=false;

GetItem(1);GetItem(2);

while (not Fin[1])or(not Fin[2]) do

begin

if Fin[1] then Winner:=2

else if Fin[2] then Winner:=1

else if Current[1].key<Current[2].key then Winner:=1

else Winner:=2;

if OutSwitch then write(g1,Current[Winner])

else write(g2,Current[Winner]);

GetItem(Winner);

end;

OutSwitch:=not OutSwitch;

end;

close(g1);close(g2);

close(f1);close(f2);

end;

procedure MergeSort(var f0:TFile);

var f1,f2,g1,g2:TFile;

i,n,k:integer;buf:Item;

flag:boolean;

begin

Assign(f1,'F1Merge.itm');

Assign(f2, 'F2Merge.itm');

Assign(g1, 'G1Merge.itm');

Assign(g2,'G2Merge.itm');

rewrite(f1);rewrite(f2);

rewrite(g1);rewrite(g2);

reset(f0);

n:=0;

while not eof(f0) do

begin

read(f0,buf);

write(f1,buf);

inc(n);

if not eof(f0) then

begin

read(f0,buf);

write(f2,buf);

inc(n);

end;

end;

flag:=true;k:=1;

Close(f1);Close(f2);Close(f0);

n:=trunc(ln(n)/ln(2))+1;

for i:=1 to n do

begin

if flag then merge(k,f1,f2,g1,g2)

else merge(k,g1,g2,f1,f2);

flag:= not flag;

k:=k*2;

end;

rewrite(f0);reset(g1);reset(f1);

if not flag then

while not eof(g1) do

begin

read(g1,buf);

write(f0,buf);

end

else

while not eof(f1) do

begin

read(f1,buf);

write(f0,buf);

end;

Close(f0);Close(g1);Close(f1);

{erase(f1);erase(g1);erase(f2);erase(g2);}

end;

begin

assign(f0,'a-file.bin');

MergeSort(f0);

end.

3. Метод злиття впорядкованих серій

В основі методу зовнішнього сортування багатошляхового злиття (злитя впорядкованих серій) лежить розподіл серій вихідного файлу по m допоміжних файлах B1, B2,..., Bm і їхнє злиття в m допоміжних файлів C1, C2,..., Cm. На наступному кроці виробляється злиття файлів C1, C2,..., Cm у файли B1, B2,..., Bm і т.д., поки в B1 або C1 не утвориться одна серія. Графічно це можна зобразити наступним чином:

36

Рис. 3. Злиття впорядкованих серій

На малюнку 3 показаний простий приклад застосування сортування збалансованим багатошляховим злиттям. Він, звичайно, занадто тривіальний, щоб продемонструвати кілька кроків виконання алгоритму, однак достатній як ілюстрація загальної ідеї методу. Помітимо, що, як показує цей приклад, у міру збільшення довжини серій допоміжні файли з більшими номерами (починаючи з номера n) перестають використовуватися, оскільки їм «не дістається» ні однієї серії. Перевагою сортування збалансованим багатофазним злиттям є те, що число проходів алгоритму оцінюється як O(log n) (n - число записів у вихідному файлі), де логарифм береться по підставі n. Порядок числа копіювань записів - O(log n). Звичайно, число порівнянь не буде менше, ніж при застосуванні методу простого злиття.

Реалізація методу мовою програмування Turbo Pascal. Нехай маємо типізований файл додатних цілочисельних даних, використовуючи метод впорядкованих серій відсортувати цей файл по зростанню.

Program Vporjadkovane_zluttja;

const max=10000;

maxint=32767;

type

Item=record

key:integer;

end;

TFile=file of Item;

var

f0:TFile;

procedure NMerge(k:integer;var f1,f2,f3,f4,g1,g2,g3,g4:TFile);

var outSwitch:1..4;

Winner:integer;

Used:array[1..4] of integer;

Fin:array[1..4]of boolean;

Current:array[1..4]of Item;

Tree:array[1..7]of Item;

History:array[1..7]of integer;

procedure CompareTree;

begin

if Tree[7].key<Tree[6].key then

begin

Tree[3]:=Tree[7];

History[3]:=History[7];

end

else

begin

Tree[3]:=Tree[6];

History[3]:=History[6];

end;

if Tree[5].key<Tree[4].key then

begin

Tree[2]:=Tree[5];

History[2]:=History[5];

end

else

begin

Tree[2]:=Tree[4];

History[2]:=History[4];

end;

if Tree[3].key<Tree[2].key then

begin

Tree[1]:=Tree[3];

History[1]:=History[3];

end

else

begin

Tree[1]:=Tree[2];

History[1]:=History[2];

end;

end;

procedure NGetItem(i:integer);

begin

if(Used[i]=k)or((i=1)and eof(f1))or((i=2)and eof(f2))or((i=3)and eof(f3))or((i=4)and eof(f4)) then

begin

Fin[i]:=True;

Tree[8-i].key:=MaxInt;

end

else

begin

case i of

1:read(f1,Current[1]);

2:read(f2,Current[2]);

3:read(f3,Current[3]);

4:read(f4,Current[4]);

end;

Tree[8-i]:=Current[i];

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

end;

CompareTree;

end;

procedure MakeTree;

var q:integer;

begin

if not eof(f1) then

begin

read(f1,Tree[7]);

History[7]:=1;

Current[1]:=Tree[7];

end;

if not eof(f2) then

begin

read(f2,Tree[6]);

History[6]:=2;

Current[2]:=Tree[6];

end;

if not eof(f3) then

begin

read(f3,Tree[5]);

History[5]:=3;

Current[3]:=Tree[5];

end;

if not eof(f4) then

begin

read(f4,Tree[4]);

Страницы: 1, 2, 3