Курсовая работа: Порівняльний аналіз ефективності та складності алгоритмів сортування файлів і послідовностей

end;

Очевидно, що після k-го кроку впорядковані ділянки мають довжину lp=2^k . Якщо 2^k =n, то масив упорядковано. Якщо 2^k >n, але 2^k-1 <n, то при виконанні останнього кроку мають місце співвідношення

lp = 2^k-1 = 2^k / 2 > n/2, npp = 0, tl = n > lp,

і злиття ділянки довжиною lp та залишку довжиною n-lp дає впорядкований масив.

Аналіз алгоритму злиття.

Оцінимо складність наведеного алгоритму. При кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2^k<2n, тобто k<1+logn, і це означає, що тіло циклу while виконується 1+ [log₂ n[ =O(logn) разів. Отже, складність алгоритму оцінюється як O(nlogn).

Запишемо в таблицю значення виразів n, n(n-1)/2, n(1+[log₂ n]) та округлене відношення r двох останніх:

n	n(n-1)/2	n(1+[log2 n])	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,' ');