Порівняльний аналіз ефективності та складності алгоритмів сортування файлів і послідовностей (стр. 2 из 3)
Запишемо в таблицю значення виразів n, n(n-1)/2, n(1+[log2n]) та округлене відношення r двох останніх:
| n | n(n-1)/2 | n(1+[log2n]) | r |
| 10 | 45 | 40 | 1 |
| 100 | 4950 | 700 | 7 |
| 1000 | 499500 | 10000 | 50 |
| 10000 | 49995000 | 140000 | 350 |
Як бачимо, кожне зростання n у 10 разів веде до зростання n(n-1)/2 та n(1+[log2n]) приблизно в 100 й 14 разів відповідно, і за n=10000 сортування злиттям виконується в сотні разів скоріше, ніж бульбашкове!
Зауважимо, що в наведеному алгоритмі сортування злиттям копіювання масиву в допоміжний указано лише для того, щоб ідею алгоритму було простіше сприйняти. Цей алгоритм нескладно переробити так, щоб замість копіювання в додатковий масив відбувалося злиття в нього упорядкованих ділянок. Отже, на кроках з номерами 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.
Рис. 1. Перший крок
Рис. 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 не утвориться одна серія. Графічно це можна зобразити наступним чином:
Рис. 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]);
History[4]:=4;
Current[4]:=Tree[4];
end;
CompareTree;
end;
begin
OutSwitch:=1;
rewrite(g1);rewrite(g2);
rewrite(g3);rewrite(g4);
reset(f1);reset(f2);
reset(f3);reset(f4);
while (not eof(f1)) or (not eof(f2))or (not eof(f3))or (not eof(f4)) do
begin
Used[1]:=1;Used[2]:=1;Used[3]:=1;Used[4]:=1;
Fin[1]:=false;Fin[2]:=false;Fin[3]:=false;Fin[4]:=false;
MakeTree;
while Tree[1].key<MaxInt do
begin
Winner:=History[1];
case OutSwitch of
1:write(g1,Current[Winner]);
2:write(g2,Current[Winner]);
3:write(g3,Current[Winner]);
4:write(g4,Current[Winner]);
end;
NGetItem(Winner);
end;
if OutSwitch=4 then OutSwitch:=1
else inc(OutSwitch);
end;
Close(g1);Close(g2);
Close(f1);Close(f2);
Close(g3);Close(g4);
Close(f3);Close(f4);
end;
procedure NMergeSort(var f0:TFile);
var f1,f2,f3,f4,g1,g2,g3,g4:TFile;
i,n,k:integer;buf:Item;
flag:boolean;
begin
assign(f1,'F1Merge.itm');
assign(f2,'F2Merge.itm');
assign(f3,'F3Merge.itm');
assign(f4,'F4Merge.itm');
assign(g1,'G1Merge.itm');
assign(g2,'G2Merge.itm');
assign(g3,'G3Merge.itm');
assign(g4,'G4Merge.itm');
rewrite(f1);rewrite(f2);
rewrite(f3);rewrite(f4);
rewrite(g1);rewrite(g2);
rewrite(g3);rewrite(g4);
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;
if not eof(f0) then
begin
read(f0,buf);
write(f3,buf);
inc(n);
end;
if not eof(f0) then
begin
read(f0,buf);