Сортування за допомогою дерева

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

Приклад двійкового дерева показано на рисунку 18.

Отже, ми вже маємо якнайменше значення елементів масиву. Щоб одержати наступний по величині елемент, спустимося від коріння по шляху; що веде до листка з якнайменшим значенням.

У цій листковій вершині ставиться фіктивний ключ з ≪нескінченно великим≫ значенням, а у всі проміжні вузли, що займалися якнайменшим елементом, вноситься якнайменше значення з вузлів - безпосередніх нащадків (рисунку 19). Процес продовжується доти, поки всі вузли дерева не будуть заповнені фіктивними ключами (рисунки 20-25).

Рисунок 18 – Перший крок.

Рисунок 19 – Другий крок.

Рисунок 20 – Третій крок.

Рисунок 21 – Четвертий крок.

Рисунок 22 – Пятий крок.

Рисунок 23 – Шостий крок.

Рисунок 24 – Сьомий крок.

Рисунок 25 – Восьмий крок.

На кожному з n кроків, що необхідні для сортування масиву, треба виконати log₂ n порівнянь. Отже, всього буде треба n*log₂ n порівнянь, але для подання дерева знадобиться 2n - 1 додаткова одиниця пам'яті.

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

Є досконаліший алгоритм, який прийнято називати пірамідальним сортуванням (Heapsort). Його ідея полягає у тому, що замість повного дерева порівняння початковий масив а[1], а[2],..., а[n] перетвориться на піраміду, що має таку властивість, що для кожного а[і] виконуються умови а[і]<= а[2і] і а[і]<= а[2і+1]. Потім піраміда використовується для сортування.

Найнаочніше метод побудови піраміди виглядає при деревовидному зображенні масиву, показаному на рисунку 26. Масив подається у вигляді двійкового дерева, корінь якого відповідає елементу масиву а[1]. На другому ярусі знаходяться елементи a[2] і а[3]. На третьому – а[4], а[5], a[6], а[7] і т.ін. Як видно, для масиву з непарною кількістю елементів відповідне дерево буде збалансованим, а для масиву з парною кількістю елементів n елемент а[п] буде єдиним (найлівішим) листком ≪майже≫ збалансованого дерева.

Рисунок 26 – Приклад пірамідального сортування.

Очевидно, що при побудові піраміди нас цікавитимуть елементи a[n/2], a[n/2-1],..., a[1] для масивів з парною кількістю елементів і елементи а[(n-1)/2], а[(n-1)/2-1],..., а[1] для масивів з непарною кількістю елементів (оскільки тільки для таких елементів істотні обмеження піраміди). Нехай /-найбільший індекс з індексів елементів, для яких існують обмеження піраміди. Тоді береться елемент а[і] у побудованому дереві і для нього виконується процедура просівання, що полягає у тому, що вибирається гілка дерева, яка відповідає min(a[2i], a[2i+1]), і значення а[і] міняється місцями із значенням відповідного елементу. Якщо цей елемент не є листком дерева, для нього виконується аналогічна процедура і т.ін. Такі дії виконуються послідовно для а[і], а[i-1],..., а[1]. Як бачимо, в результаті ми одержимо деревовидне подання піраміди для початкового масиву (послідовність кроків для використовуваного в наших прикладах масиву показана на рисунках 27-30).

Рисунок 27 – Пірамідальне сортування. Крок 1.

Рисунок 28 – Пірамідальне сортування. Крок 2.

Рисунок 29 – Пірамідальне сортування. КрокЗ.

Рисунок 30 – Пірамідальне сортування. Крок 4.

Рисунок 31 – Блок-схема Рисунок 32 – Блок-схема побудови

методу впорядкування піраміди та її перевірки.

піраміди.

9 Побудова піраміди методом Флойда

1964 року Флойд запропонував метод побудови піраміди без явної побудови дерева (хоча метод заснований на тих самих ідеях). Побудова піраміди методом Флойда для нашого стандартного масиву показана в таблиці 7.

Таблиця 7 – Приклад побудови піраміди.

Початковий стан масиву	8 23 5 |65| 44 33 1 6
Крок 1	8 23 |5| 6 44 33 1 65
Крок 2	8 |23| 1 6 44 33 5 65
Крок 3	|8| 6 1 23 44 33 5 65
Крок 4	1 6 8 23 44 33 5 65
1 6 5 23 44 33 8 65

У таблиці 8 показано, як здійснюється сортування з використанням побудованої піраміди. Суть алгоритму полягає в подальшому. Нехай i – найбільший індекс масиву, для якого вказані умови піраміди. Тоді, починаючи з а[1] до а[і] виконуються такі дії.

Таблиця 8 – Сортування за допомогою піраміди.

Початкова піраміда	1 6 5 23 44 33 8 65
Крок 1	65 6 5 23 44 33 8 1
5 6 65 23 44 33 8 1
5 6 8 23 44 33 65 1
Крок 2	65 6 8 23 44 33 5 1
6 65 8 23 44 33 5 1
6 23 8 65 44 33 5 1
Крок 3	33 23 8 65 44 6 5 1
8 23 33 65 44 6 5 1
Крок 4	44 23 33 65 8 6 5 1
23 44 33 65 8 6 5 1
Крок 5	65 44 33 23 8 6 5 1
33 44 65 23 8 6 5 1
Крок 6	65 44 33 23 8 6 5 1
44 65 33 23 8 6 5 1
Крок 7	65 44 33 23 8 6 5 1

На кожному кроці вибирається останній елемент піраміди (у нашому випадку першим буде вибраний елемент а[8]). Його значення міняється зі значенням а[1], після чого для а[1] виконується просіювання. При цьому на кожному кроці кількість елементів в піраміді зменшується на 1 (після першого кроку як елементи піраміди розглядаються а[1], а[2],..., а[n-1]; після другого – а[1], а[2],..., а[n-2] і т.ін., поки в піраміді не залишиться один елемент). Легко побачити (це ілюструється в таблиці 8), що як результат ми одержимо масив, впорядкований у порядку спадання. Можна модифікувати метод побудови піраміди і сортування, щоб одержати впорядкування у порядку зростання, якщо змінити умову піраміди а [і]>=а[2і] і а[1]>=а[2i+1] для всіх значень індекса i.

Процедура сортування з використанням піраміди вимагає виконання порядку nlog₂n кроків у гіршому разі, що робить її особливо привабливою для сортування великих масивів.