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

Досягненням мети й відповідно до поставленої гіпотези визначаються наступні завдання:

1. Вивчити літературу по темі алгоритми сортування файлів;

2. Проаналізувати зовнішні методи сортування;

3. Реалізувати на Turbo Pascal алгоритми сортування файлів довільної величини;

4. Розробити закінчений програмний продукт по темі дослідження;

5. Провести аналіз математичних моделей різних методів.

1. Сортування прямим злиттям

Перш ніж розглядати зовнішні алгоритми сортування, давайте подумаємо, яким же чином можна відсортувати величезний файл, що не поміщається в оперативній пам’яті? Перше, що приходить на розум, це взяти його, розбити на велику кількість файлів і відсортувавши кожен потім злити. Тому, давайте розглянемо приклад злиття двох відсортованих масивів та проведемо аналіз швидкості його виконання.

Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається – тоді решта іншої колони додається до нової.

Нехай у масиві Y з елемента Y[m] починається впорядкована ділянка довжиною s, а з елемента Y[m+s] – впорядкована ділянка довжини r. Наприклад,

Y	…	1	3	…	13	2	4	…	88
…	M	m+1	m+s-1	m+s	m+s+1	…	m+s+r

Результатом злиття повинна бути ділянка довжини r+s у масиві X:

X	…	1	2	3	4	…	13	…	88
…	m	m+1	m+2	m+3	…	m+s+r

Дане злиття двох ділянок у масиві Y у ділянку масиву X задає процедура:

procedure mrg(var Y: ArT; m, s, r: Indx; var X: ArT);

var mr, k: Indx; i, j: Extind;

begin

mr:= m + s; { mr – початок правої частини }

i:= m; j:= mr; { i та j пробігають ліву й праву ділянки масиву Y}

for k:= m to m + s + r - 1 do {заповнення X[m], …, X[m+s+r-1]}

if i > m + s - 1 then begin X[k]:= Y[j]; j:= j + 1 end

else if j > mr + r - 1 then

begin X[k]:= Y[i]; i:= i + 1 end else

if Y[i] < Y[j] then

begin X[k]:= Y[i]; i:= i + 1 end else

begin X[k]:= Y[j]; j:= j + 1 end

end;

Тепер розглянемо сортування масиву A злиттям. На першому кроці елементи A[1], …, A[n] копіюються в допоміжний масив B[1], …, B[n]. Його елементи розглядаються парами B[1] і B[2], B[3] і B[4] тощо, як упорядковані послідовності довжиною lp = 1 і зливаються за допомогою процедури mrg в масив A. Тепер там є впорядковані ділянки довжиною 2. За непарного n останній елемент A[n] залишається без змін як послідовність довжиною 1.

На наступному кроці після копіювання в масив B зливаються пари упорядкованих ділянок B[1]B[2] і B[3]B[4], B[5]B[6] і B[7]B[8] тощо. З'являються впорядковані ділянки довжиною 4. Нехай t=n mod 4 – довжина залишку масиву після останньої повної четвірки елементів. При t=1 або t=2 останні t елементів утворюють упорядковану ділянку після попереднього кроку. При t=3 зливаються упорядкована пара B[n-1]B[n-2] та ділянка B[n] у ділянку довжиною t.

Кроки повторюються з подвоєнням довжин упорядкованих ділянок lp, поки lp < n.

Розглянемо сортування злиттям масиву <11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1> довжини n=11. Упорядковані послідовності в ньому вказуються в дужках <>, а пари таких, що зливаються, відокремлені ";":