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

Завдання

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

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

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

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

1. Проаналізувати покрокове виконання завдань 3—4.

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

6. Порівняти результати роботи алгоритму сортування ме­тодом Шелла та алгоритму метода прямого включения для зав-дань 3—6.

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

Пірамідальне сортування, або сортування деревом

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

166

зустрічається шд назвою «пірамідальне сортування», «сорту -вання деревом», або «сортуваннякупою». Чому цетак, розгля-немо на відомому нам уже прикладі масиву:

44, 55, 12, 42, 94, 18, 06, 67.

Що таке бінарне дерево, ми вже знаємо. Тому давайте пред-ставимо заданий масив саме у вигляді такого дерева (мал. 58), позначаючи кожну його вершину порядковим номером даного елемента у заданому масиві.

Мал. 58

На перший погляд нічого закономірного в цьому дереві не видно. Елементи розташувалися в ньому по рівнях так само, як у збалансованому дереві.

А тепер давайте представимо у вигляді бінарного дерева (мал. 59) той самий масив, відсортований у порядку спадання: 94, 67, 55, 44, 42, 18, 12, 06.

Мал. 59

Тепер, порівнюючи малюнки 58 і 59, можна побачити, що елементи бінарного дерева, побудованого зі значень відсортова-ного масиву, мають таку ознаку: кожний елемент дерева не менший, ніж yci елементи, для яких він є батьківським. Крім того, індекси елементів масиву, які відповідають цим верши­нам дерева, мають чіткий взаємозв'язок. Якщо розглянути еле­мент масиву з порядковим номером і, то його безпосередніми нащадками у дереві будуть елементи масиву з номерами 2і - лі-вий нащадок і 2і + 1 - правий. 3 іншого боку, елемент масиву, який є батьківським для елемента з індексом і, буде мати ін-декс [i/2] (i div 2).

167

Бінарне дерево, для будь-якої вершини якого виконуються одночасно дві умови a_t > а_и та а_; > о_2і , називається піра-мідою, або бінарною купою.

Зрозуміло, що для термінальних вершин піраміди такі умо­ви не виконуються, оскільки у них не існує нащадків. 3 наведе-ного означения можна зробити логічний висновок, що у вер­шин! піраміди завжди буде найбільший елемент.

Упорядкований за спаданиям масив завжди утворює піра-міду! Це видно з малюнка 59. А чи це єдиний варіант піраміди, тобто бінарного дерева, що відповідає означению піраміди? Спробуємо перетворити початковии масив, зображении на малюнку 58, у піраміду.

Будемо робити це так: піднімаючись рівнями від терміналь-них вершин дерева до кореневої, будемо впорядковувати еле-менти, що знаходяться у вершинах, за правилами піраміди (мал. 60).

Д) е)

Мал. 60

За п'ять кроків ми перетворили бінарне дерево, зображене на малюнку 58, у піраміду, тобто для кожної вершини вико-

168

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

Як же виглядає тепер перетворений масив? Запишемо зна­чения вершин отриманої піраміди (мал. 60, д) у вигляді маси­ву: 94, 67, 18, 44, 55, 12, 06, 42.

Давайте спробуємо відновити дії, зображені на бінарному дереві з перетворення його на піраміду, на самому масиві (мал. 61).

а)

r)

Д)

e)

Мал. 61

kflMHTHKit, !' I'¹ *•' I

169

Який висновок можна зробити, аналізуючи перетворення масиву, зображеного на малюнку 61?

По-перше, наибольший елемент «піднявся» в корінь дерева, тобто на початок масиву. Тому надалі його можна запам'ятати і виключити з наступного перегляду масиву.

По-друге, на малюнку 60, г, д та малюнку 61, г, д видно, що, для того аби зберегти структуру піраміди, доводиться інколи виконувати декілька кроків, навіть якщо вершини, для яких це робиться, не є коренем дерева. Наприклад, після виконання обміну 44 ** 94 (мал. 60, г) виявилося порушення умови піра-міди у вершит з номером 2 (мал. 61, д). Для відновлення піра-міди треба було зробити ще один обмін 44 *» 67. Отже, можна зробити висновок: виконання обмінів відбувається від термі-нальних вершин до кореневої, але коли місце обміну в дереві визначене, то надалі обмін виконується від цієї вершини вниз у напрямі до термінальних вершин доти, доки не відновиться структура піраміди.

По-третє, є певна закономірність між індексами елементів масиву, які міняємо місцями. Аналізуючи піраміду, зображе-ну на малюнку 58, зазначали, що кожен і-ий елемент масиву, який знаходиться у вершині піраміди, мае нащадків із по-рядковими номерами у масиві 2і та (2і + 1) для і < [п/2]. Це можна спостерігати на малюнку 61: обмін відбувається саме між такими елементами у масиві 8*»4,6*»3,5**2,2**1.

До речі, якщо в наведеному прикладі методом прямого об-міну ми знаходили найбільший (або найменший) елемент за 8 порівнянь і обмінів, то в даному разі - за 4. Слід погодитися, що це досить значне удосконалення.

Як визначити, за яку кількість кроків можна підняти най-більший елемент у корінь бінарного дерева? Це залежить від глибини дерева, яке можна побудувати із заданого масиву. Наш масив утворив піраміду з 4 рівнями, тому проходження ними і є тією кількістю кроків k, які необхідні для отримання у вершині найбільшого елемента. Оскільки маємо справу з бі-нарним деревом, то кількість кроків можна визначити як мак-симальне k, для якого справедлива залежність 2* < га, збіль-шене на 1, бо в дереві є нульова вершина.

Повернемося до нашого алгоритму. Оскільки найбільший елемент масиву отримано, то доречно було б його десь окремо запам'ятати і застосувати описаний алгоритм побудови піра-міди та підняття найбільшого елемента у ньому в корінь дерева для тієї частини масиву, що залишилася.

На малюнках 62—69 зображено два основні моменти нашого алгоритму:

- побудову бінарного дерева для фрагмента масиву на дано­му крощ;

170

- «підняття» найбільшого елемента в корінь бінарного дере­ва шляхом побудови піраміди.

На зазначених малюнках будемо зображати покроково ро­боту описаного алгоритму як у вигляді піраміди, так і у вигля-ді послідовності елементів масиву. Це буде надалі корисним під час розбору реалізації алгоритму пірамідального сортування.

Мал. 62

_©

Мал. 63