Материал: Інформатика_1 (методи побудови алгоритмівта та їх аналіз)

_'Ir-r-J'

k

I Ы 19 лам ;

/*т*Ч

186

Мал. 80

Схематично описаний процес злиття заданого масиву можна зобразити так, як показано на малюнку 81.

вхіднии масив

вихіднии масив

А тепер перейдемо до кодування алгоритму прямого злиття MergeSort у вигляді тексту Pascal-програми. Запишемо спочат-ку процедуру злиття в загальному вигляді:

procedure MergeSort; var i, j, k, I: integer;

up: boolean; p: integer; begin

{Визначення індексів.}

up :=true; p := 1; repeat if up then begin

| i:=1;j:=n;k:=n + 1;l:=2*n end else begin

| k:=1;l:=n;i:=n+1;j:=2*n end; <Алгоритм злиття р-наборів з / тау'-входів у к та /-виходи.> up := not (up); p := 2 * p; until p = n; end;

Уточнимо ту частину алгоритму, яка безпосередньо виконує процес злиття та працюе для будь-якого п, увівши ще й такі змінні: т - кількість елементів, які ще залишилося обробити; q та г - довжини підпослідовностей, що зливаються.

Оскільки п не завжди є степенем 2, то умовою виходу буде р > п. 3 цієї причини підпослідовності з q та г елементів не завжди зійдуться в центрі. Тому залишки копіюватимемо у кінець вихідної послідовності.

Отже, уточнений і повний алгоритм прямого злиття у вигля-ді тексту Pascal-програми такий:

procedure StraightMerge; var i, j, k, I, t: integer; h, m, p, q, r: integer;

8*

187

up: boolean; begin

up := true; repeat

h:= 1; m :=m; if up then begin

| i := 1; j := n; к := n + 1; I := 2 * n end else begin

| k:= 1;l:=n;i:=n + 1;j:=2*n end; repeat {Злиття серій з /' та/'-входів у /с-вихід.)

if m > = р then q := p else q := m; m := m - q;

if m > = r then r := p else r := m; m :=m- r;

while (q <> 0) and (r <> 0) do {Злиттядтагелементів.}

ifa[i]<a[j] then begin

a[k]:=a[i];k:=k + h; i := i + 1; q := q - 1 end else begin

a[k] :=a[j];k:=k + h; j:=j-1;r:=r-1 end; while r > 0 do begin

a[k]:=a[j];k:=k + h; j := j - 1; r := r- 1 end; while q > 0 do begin

a[k]:=a[i];k:=k + h; i :=i+ 1; q :=q - 1 end;

{Перемикання на кінець вихідного файла) h := - h; t := k; k := I; I := t; {для рівномірного розподілу.)

until m = 0;

up := not up; p := 2 * p; until p > ■ n; if not up then for i := 1 to n do a[i] :=a[i + n]; end;

188

Описаний алгоритм був запропонований Н. Віртом, і саме тому ми надали йому перевагу. Але виникає слушне запитан-ня: а чи можна його спростити? Так, звичайно. Можна знехту-вати перемиканням вхідної та вихідної частил подвійного за дЪвжиною масиву. Для цього ввести ще один масив такої самої довжини, як і заданий. Злиття робити у цей додатковий масив, переписуючи згодом упорядковані частини з нього в заданий масив.

Наведемо текст Pascal-програми іншого алгоритму прямого злиття двох підпослідовностей і пропонуємо вам розібратися в ньому самостійно.

Спочатку розглянемо процедуру, що реалізує алгоритм двох сусідніх серій в одну:

procedure merger (var one, two: mas); var q, x, y, en: word; begin x:=i; у :=i + k; if i + 2 * k - 1 > n then en := n else en := i + 2 * k — 1; for q := i to en do

if (x <= i + k - 1) and (y <= en) then

if (one[x]<one[y])

then begin two[q] := one[x]; inc (x) end else begin two[q] := one[y]; inc (y) end else

if x>i + k-1

then begin two[q] := one[y]; inc (y) end else begin two[q] := one[x]; inc (x) end; end;

Основна частина алгоритму передбачає поділ масиву на серії довжиною 2*~\ для k = 1, 2, ..., та наступив їх злиття. Робота відбувається почергово з масивами а та Ь: з одного масиву ін-формація береться як із вхідного, а в другий записуеться як у вихідний. На наступному проході масиву з подвоєною кіль-кістю елементів серїї масиви міняються місцями за призна-ченням:

flag := true; k:=1;

while k<n do begin

i:=1;

whilei < n- k+ 1 do

189

begin

if flag then merger (a, b) else merger (b, a); inc (i, 2 * k); end; if i <= n then if flag

then for j := i to n do b[j] := a[j] else for j :-itondoa[j] :=b[j]; k:=k*2; flag := not flag end;

Оцінимо ефективність роботи алгоритму прямого злиття. Маємо справу з подвоєнням розмірів частин масиву, які зли-ваються. Раніше (у методах швидкого та пірамідального сорту-вання) ми, навпаки, поділили масив навпіл, переміщалися бі-нарним деревом у попіуках елементів для обміну. Але від цього кількість кроків, необхідних для впорядкування масиву, не змінюється. Однак за умовою алгоритму сортування припи-няється, коли р > п, і залишок елементів, кількість яких мен-ша зар, просто переписуємо у вихідний масив. Тому насправді для методу прямого злиття необхідно [log₂n] проходів масиву. I загальною оцінкою даного методу є 0(п [log₂n]).

Оскільки метод прямого злиття працює не для всіх типів змінних і розмірностей масивів, то при його тестуванні треба збалансувати ці два фактори для п > 100. Вхідні дані, на яких рекомендується протестувати розроблений алгоритм, тра-диційно повинні бути такими:

• вхідний масив уже впорядкований необхідним чином;

• вхідний масив є частково впорядкованим;

• вхідний масив упорядкований у зворотному порядку;

• елементи вхідного масиву розміщені випадковим чином.

/ Запитання для самоконтролю

1. Для яких сукупностей елєментів були свого часу запропоновані методи сортування? Як називаються такі сукупності елементів?

2. Яка технічна проблема спричинила розробку цих методів сорту­вання?

3. У чому полягає ідея методу прямого злиття для сортування еле-мент'ш?

4. Наведіть власний приклад сортування восьми елементів ме­тодом прямого злиття. Проілюструйте алгоритм методу прямо­го злиття на наведеному прикладі.

5. Запишіть алгоритм злиття в упорядковану послідовність двох масивів з п елементів кожний.

6. Як можна модифікувати алгоритм, наведений у запитанні 5, для впорядкування елементів заданого одновимірного масиву?

190

7. Схематично зобразіть роботу алгоритму, наведеного у запитан-ні 6, на конкретному прикладі.

8. Запишіть алгоритм і текст Pascal-процедури MergeSort, що реалізує метод прямого злиття для сортування елементів одно-вимірного масиву.

9. Який ще варіант реалізації алгоритму сортування елементів ма­сиву методом прямого злиття можна запропонувати? Обґрун-туйте його та запишіть фрагмент алгоритму і текст Pascal-npo-грами.

10. Якою є оцінка ефективності роботи лінійного пошукового алго­ритму? Обґрунтуйте свою відповідь.

Завдання

1. Реалізувати у вигляді програми алгоритм сортування за­дано!' послідовності за зростанням методом прямого злиття.

2. Модифікувати алгоритм, реалізований у завданні 1, так, щоб сортування відбувалося за спаданиям.

3. Протестувати реалізовані в завданнях 1-2 алгоритми для масиву 15, 4, 10, 8, 6, 9, 16, 1, 7, 3,11,14, 2, 5,12, 13.

4. Проаналізувати покрокове виконання завдання 3 щодо кількості виконуваних дій.

5. Підібрати власні тести, які доводить переваги й показу -ють недоліки сортування вхідних даних методом прямого злит­тя при п > 100.

6. Зробити письмовий аналіз завдань 3-5.

Метод природного злиття

При прямому злитті не можна скористатися тією перевагою, що дані, можливо, вже частково впорядковані, оскільки весь час зливали підпослідовності, однакові за кількістю елементів. Ми не звертали уваги на те, що більші за кількістю фрагменти масиву, можливо, уже утворюють упорядковану підпослідов-ність.

Пропонується метод NaturalMerge, в якому в групи виді-ляються вже впорядковані підпослідовності, які ще носять на-зву серій, або максимальних сєрій. Отже, максимальною серією називатимемо підпослідовність а,,..., а., що задовольняє умову:

(а_1Л > a) n(a_k<a_k^(i<k<. j)) П (a_j >а_{/ + 1}).

Завдання полягатиме у виділенні таких послідовних серій та їх наступному злитті.

Нехай с - задана послідовність, а та b - сусідні серії. Схема­тично алгоритм методу природного злиття можна зобразити так (мал. 82):

191

фаза фаза

розподілу злиття

прохід 1

прохід 2

Мал. 82

прохід п

Отже, за кожний прохід заданого масиву зчитуємо дві сусід-ні серії (а₍ та Ь₍), зливаємо їх і записуємо на свое місце в с і т. д.

Що може статися? Може виникнути ситуація, коли отри-маемо непарну кількість серій. Тоді остання непарна серія буде переписана у с без змін.

Розглянемо такий приклад (мал. 83).

ПроХІД 1 -* U7|3/|05|59|/3|4;U3|67l/il23|29U7|03|07|7/|02|/9J57|37|6/|

прохІД 2 -» [05\17\31 \59\ll 13 23 29 41 43 47 67 02 03 07 19 57 7l\37\6l\

Мал. 83

Сформулюемо алгоритм природного злиття у вигляді ок-ремих пунктів:

1. розділити елементи заданого масиву на окремі серії, ви-значивши індекси початку й кінця кожної з них;

2. злити визначені серії, переписавши результати злиття в заданий масив;

3. зменшити кількість серій удвічі;

4. якщо кількість серій більша за 1, то визначити нові ін-декси початку й кінця кожної із серій і перейти до пункту 2.

Згідно з нашим алгоритмом треба на першому кроці сорту-вання визначати кількість серій, що зливаються, а потім лише

192

вдвічі зменшувати їх кількість. Ознакою завершения сортуван-ня є «кількість серій дорівнює 1». Взагалі з кожним наступним проходом кількість серій справді зменшується вдвічі (або т/2 + 1), і саме це може бути визнано критерієм завершения алгоритму. Однак може скластися ситуація, що кількість кро-ків ще не вичерпана, а послідовність уже впорядкована. Роз-глянемо такий приклад (мал. 84).