Міністерство освіти і науки України
Курсова робота на тему:
Порівняльний аналіз ефективності та складності алгоритмів сортування файлів і послідовностей
Зміст
Вступ
1. Сортування прямим злиттям
2. Природне злиття
3. Метод злиття впорядкованих серій
4. Багатофазне злиття
Висновки
Література
Додатки
Вступ
Комп’ютери тісно увійшли в наше життя. Ми і не помітили, як вони заполонили всі галузі нашого господарства, зайдеш в супермаркет – візьмеш товар, тобі автоматично виб’ють чек за штрих кодом, в бібліотеку зайдеш – по каталогу знайдуть потрібну книжку і скажуть в якому ряду і на якій полиці вона розміщена. Потрібно знайти реферат, - будь-ласка, заходиш в Інтернет-кафе, відкриваєш пошуковий сервер, вводиш слова із потрібної теми і вже за секунду тобі відкриваються посилання на можливі сайти. Аналогічним чином ви заходите в магазин і замовляєте вкрай необхідну деталь для вашої пральної машини і вже за секунду вам повідомляють чи є вона на прилавку магазину, чи можливо лежить неподалік на складі чи її зможуть замовити і привезти наступного тижня.
Проте рідко хто задумувався, як так швидко ви отримуєте цю інформацію? А все дуже просто, існує певна база даних, по ній проводиться пошук і вже по результатах вибірки робляться висновки. Зрозуміло, рядовому користувачу вникати в деталі неважливо, проте ми в своїй курсовій роботі зачепимо ряд питань.
Так, пошук проводиться в базі даних. Для того щоб він був швидкий, база даних повинна бути впорядкована. Отже, хоч програмування містить цілу низку важливих внутрішніх задач, та все ж однією з найбільш важливих таких задач для програмування є задача сортування. Під сортуванням звичайно розуміють перестановки елементів будь-якої послідовності у визначеному порядку. Ця задача є однією з найважливіших тому, що її метою є полегшення подальшої обробки певних даних і, насамперед, задачі пошуку. Так, одним з ефективних алгоритмів пошуку є бінарний пошук. Він працює швидше ніж, наприклад, лінійний пошук, але його можливо застосовувати лише за умови, що послідовність вже упорядкована, тобто відсортована.
Взагалі, відомо, що в будь-якій сфері діяльності, що використовує комп’ютер для запису, обробки та збереження інформації, усі дані зберігаються в базах даних, які також потребують сортування. Певна впорядкованість для них дуже важлива, адже користувачеві набагато легше працювати з даними, що мають певний порядок. Так, можна розташувати всі товари по назві або відомості про співробітників чи студентів за прізвищем або роком народження, тощо.
Задача сортування в програмуванні не вирішена повністю. Адже, хоча й існує велика кількість алгоритмів сортування, все ж таки метою програмування є не лише розробка алгоритмів сортування елементів, але й розробка саме ефективних алгоритмів сортування. Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв’язків задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все ефективність за часом та економне використання пам’яті. Згідно цих вимог, прості алгоритми сортування (такі, як сортування вибором і сортування включенням) не є дуже ефективними.
З винайденням комп’ютерної техніки проблемою створення алгоритмів сортування займалося дуже багато людей. Проводилися досліди, експерименти із швидкодії одних методів і їх переваги над іншими, наводилися їх математичні моделі для оцінки затраченого часу виконання.
З часом, ці методи були розбиті на декілька категорій, найбільш відомі серед яких, це прямі методи сортування масивів і послідовностей:
- сортування прямим включенням.
- сортування бінарним включенням.
- сортування прямим вибором.
- сортування прямим обміном.
Та швидкі методи сортування:
- сортування алгоритмом Шелла;
- сортування алгоритмом Quick Sort;
- сортування алгоритмом Тree Sort;
- сортування алгоритмом Heap Sort.
Звичайно, це не всі методи сортування масивів. Та з часом виявилося, що вони не повністю вичерпують проблеми пов’язані із питанням сортування. Так, в реальних задачах виникають послідовності, що зберігаються в файлах і не можуть уміщатися в оперативній пам'яті у вигляді масивів. Наприклад, у великому місті може бути кілька мільйонів абонентів телефонної мережі. Звичайно, для швидкого пошуку дані про абонентів мають бути відсортованими. Виникає задача сортування файлів за умови, що файли цілком не можна подавати в оперативній пам'яті. Тому, алгоритми сортування стали ще умовно поділяти не лише на прямі та швидкі а і на внутрішні (ті що обробляються оперативною пам’яттю) та зовнішні.
Метою роботи є: Знайомство з теоретичним положенням, що стосуються методів сортування файлів, реалізація їх на мові програмування Turbo Pascal.
Предмет дослідження: Зовнішні алгоритми сортування послідовностей.
Об'єкт дослідження: Математична модель доцільності використання зовнішніх алгоритмів сортування на практиці.
Досягненням мети й відповідно до поставленої гіпотези визначаються наступні завдання:
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. Упорядковані послідовності в ньому вказуються в дужках <>, а пари таких, що зливаються, відокремлені ";":
< <11><10>; <9><8>; <7><6>; <5><4>; <3><2>; <1> >, lp=1
< <10, 11><8, 9>; <6, 7><4, 5>; <2, 3><1> >, lp=2
< <8, 9, 10, 11><4, 5, 6, 7>;<1, 2, 3> >, lp=4
< <4, 5, 6, 7, 8, 9, 10, 11><1, 2, 3> >, lp=8
<1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11>, lp=16, lp³ n.
Як бачимо, нам знадобилося 4 кроки злиття для того, щоб одержати впорядований масив.
Даний спосіб сортування можна описати наступною процедурою Mrgsort:
procedure Mrgsort (var A: ArT; n: Indx);
var B: ArT;
lp, npp, cpp, bpp, tl: integer;
begin
lp:= 1;
while lp < n do
begin
B:= A; { копіювання }
npp:= n div (2*lp); { кількість пар ділянок }
tl:= n mod (2*lp); { довжина залишку }
for cpp:= 1 to npp do { cpp – номер пари }
begin
bpp:= (cpp - 1)*2*lp + 1;
{ індекс першого елемента лівої ділянки пари}
mrg (B, bpp, lp, lp, A);
end;
{ обробка залишку }
if tl > lp then
mrg (B, n - tl + 1, lp, tl - lp, A);
{ за tl <= lp залишок був упорядкований }
{ на попередньому кроці }
lp:= lp*2
end;
{ lp >= n: масив упорядковано на останньому кроці }
end;
Очевидно, що після k-го кроку впорядковані ділянки мають довжину lp=2k. Якщо 2k=n, то масив упорядковано. Якщо 2k>n, але 2k-1<n, то при виконанні останнього кроку мають місце співвідношення
lp = 2k-1 = 2k / 2 > n/2, npp = 0, tl = n > lp,
і злиття ділянки довжиною lp та залишку довжиною n-lp дає впорядкований масив.
Аналіз алгоритму злиття.
Оцінимо складність наведеного алгоритму. При кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2k<2n, тобто k<1+logn, і це означає, що тіло циклу while виконується 1+ [log2n[ =O(logn) разів. Отже, складність алгоритму оцінюється як O(nlogn).