Програмування та відлагодження алгоритму внутрішнього сортування методом злиття

Міністерство освіти і науки України  

Вінницький національний технічний університет  

Факультет інтелектуальних інформаційних технологій та автоматизації  

Кафедра КН  

Лабораторна робота №5  

 з дисципліни «Теорія алгоритмів»  

Виконав: ст. гр. 5КН-22б. Столяр П.М    

Перевірив асистент: Денисюк В.О.    

Вінниця 2023

 Лабораторна робота № 5  

Тема: програмування та відлагодження алгоритму внутрішнього сортування  методом злиття. Визначення складності алгоритму та часу його виконання.

Мета: проаналізувати та дослідити алгоритм сортування шляхом злиття.  

Теоретичні відомості  

1 Сортування методом злиття Існує багато стандартних прийомів, які  використовуються під час побудови алгоритмів. Наприклад, сортування  вставками застосовує алгоритм, що діє покроково: ми додаємо елементи один  за одним до відсортованої частини масиву. У цій лабораторній роботі  розглянемо інший підхід, який називають „розділяй і володарюй”, і побудуємо  за його допомогою значно швидший алгоритм сортування. Принцип „розділяй і  володарюй”. Багато алгоритмів за своєю природі рекурсивні, тобто  розв’язуючи деяку задачу, вони викликають самих себе для розв’язання її  підзадач. Ідея принципу „розділяй і володарюй” полягає саме в цьому.  Спочатку задача розбивається на декілька підзадач меншого розміру. Потім ці  задачі розв’язуються (за допомогою рекурсивного виклику або безпосередньо,  якщо розмір досить малий). Нарешті, їх розв’язки комбінуються і ми  отримуємо шуканий розв’язок вихідної задачі [1 – 4]. Для задачі сортування ці  три етапи виглядають так. Спочатку ми розбиваємо масив на дві половини  меншого розміру. Потім ми сортуємо кожну з половин окремо. Після цього нам  залишається з’єднати два впорядкованих масиви половинного розміру в один.  Рекурсивне розбивання задачі на менші відбувається доти, поки розмір масиву  не cтане одиничним (будь-який масив розміром 1 можна вважати  впорядкованим) [1]. Нетривіальним етапом є з’єднання двох впорядкованих  масивів в один. Воно виконується за допомогою допоміжної процедури  MERGE( A, p,q,r). Параметрами цієї процедури є масив А і числа p, r, q , що  вказують границі ділянок, які зливаються. Процедура передбачає, що p q r ≤ < ,  а ділянки A p...q [ ] та A q 1...r [ + ] вже відсортовані, і зливає їх в одну ділянку  A p...r [ ]. Зрозуміло, що час роботи процедури MERGE є θ (n), де n − загальна  довжина ділянок, що зливаються n r p 1 = − + . Це легко пояснити на звичайних  гральних картах. Нехай ми маємо дві стопки карт (сорочкою 2 вниз), і у кожній  карти йдуть зверху вниз у порядку зростання. Для об’єднання цих стопок в  одну на кожному кроці ми беремо меншу із двох верхніх карт і кладемо її  (сорочкою вверх) у результуючу стопку. Коли одна з вихідних стопок стає  порожньою – ми додаємо всі карти, що залишилися другої стопки до  результуючої стопки. Отже, кожен крок вимагає обмеженого числа дій, і  загальне число дій становить θ (n) [1]. Тепер напишемо процедуру сортування

злиттям MERGESORT( A, p,r), яка сортує ділянку A p...r [ ] масиву А, не  змінюючи іншої його частини. При p r ≥ ділянка містить максимум один  елемент, і, отже є відсортованою. У протилежному випадку ми шукаємо число  q , що ділить ділянку на дві приблизно рівні частини A p...r [ ] (містить ⎡ ⎤ n / 2 ⎢

⎥ елементів) і A q 1...r [ + ] (містить ⎢ ⎥ n / 2 ⎣ ⎦ елементів). Нагадаємо, що через ⎢ ⎥ x⎣ ⎦ ми позначаємо цілу частину x (найбільше ціле число, яке менше або  дорівнює x), а через ⎡ ⎤ x⎢ ⎥ − найменше ціле число, яке > або = x. Весь масив тепер можна відсортувати за допомогою виклику MERGESORT ( A,1,length A[ ]). Якщо довжина масиву n=length[A] є степенем двійки, то у  процесі сортування відбудеться злиття пар елементів у відсортовані ділянки  довжиною 2, потім злиття пар таких ділянок у відсортовані ділянки довжиною  4 і так далі до n (на останньому кроці з’єднуються дві відсортованих ділянки  довжиною n/2). Цей процес наведено на рисунку 1.