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

Піраміда, вона ж дерево Уявіть собі, що ми розташували елементи масиву рядками, щоразу подвоюючи їх кількість: у першому рядку – перший елемент, у другому – елементи з індексами 2, 3, у наступному – 4, 5, 6, 7, далі 8, 9, 10, 11, 12, 13, 14, 15 тощо. Останній рядок може виявитися неповним.

Наприклад, за кількості елементів n=12 маємо таку піраміду індексів:

1

2 3

4 5 6 7

8 9 10 11 12

Елементи цієї піраміди будемо називати вузлами. Між вузлами проведемо стрілки: від 1 – до 2 та 3, від 2 – до 4 та 5, від 3 – до 6 та 7 тощо, тобто від кожного вузла k до 2k та 2k+1, де k<n div 2 (рис.17.1). За парного n від вузла (n div 2) проводиться стрілка лише до вузла n. Вузли 2k та 2k+1 називаються синами вузла k, який називається їхнім батьком. Вузол 1 називається вершиною піраміди. Кожний вузол також можна вважати вершиною піраміди, складеної ним, його синами, їх синами тощо.

Наприклад, вузол 2 є вершиною піраміди, складеної з 2, 4, 5, 8, 9, 10, 11, вузол 3 – піраміди з 3, 6, 7, 12. Піраміду можна розглядати як дерево, гілки якого – стрілки від батьків до синів. Вершина піраміди називається коренем дерева. Припустимо тепер, що значення елементів масиву розташовано так, що значення кожного елемента-батька не менше значень його синів:

A[1] ³ A[2] та A[1] ³ A[3], A[2] ³ A[4] та A[2] ³ A[5] тощо.

Отже, за кожного k=1, 2, … , n div 2 A[k] ³ A[2*k] та A[k] ³ A[2*k+1] (за парного n елемент A[n div 2] має лише одного сина A[n]).

Наприклад,

30

12 30

12 5 29 2

11 10 3 2 28 27

Цій піраміді відповідає послідовне розташування <30, 12, 30, 12, 5, 29, 2, 11, 10, 3, 2, 28, 27>. Очевидно, що кожний елемент має значення, найбільше в тій піраміді, де він є вершиною. Наприклад, A[2] має значення, найбільше серед елементів із індексами 2, 4, 5, 8, 9, 10, 11. Зокрема, A[1] має значення, найбільше серед усіх елементів.

Якщо поміняти місцями значення A[1] і A[n], то елемент A[n] матиме найбільше значення. Про нього "можна забути" та зосередитися на сортуванні A[1], A[2], . , A[n-1]. Зрозуміло, що умова A[1]³ A[2], A[1]³ A[3] після обміну може виявитися порушеною. Для її відновлення треба обміняти місцями значення A[1] та того з A[2], A[3], чиє значення максимальне.

Нехай це буде A[3]. В останньому прикладі після обміну значень A[1] і A[12] на вершині піраміди значення 27, і 27<30, тобто A[1]<A[3]. Після обміну їх значень умова може порушитися в піраміді з вершиною A[3]. Відновимо цю умову так само, як і для вершини A[1], опустившися при цьому до вузла A[6] чи A[7]. І так далі. Після відновлення умови можна буде обміняти значення першого елемента з передостаннім, "забути" про нього, знову відновити умову, знову загнати перше значення в кінець тощо.

Нехай процедура bld(A, n) задає початкову перестановку значень масиву таким чином, що виконується умова , а процедура reorg(A, i, k) – її відновлення у частині масиву A[i], … , A[k]. Тоді за дії означень сортування задається процедурою Treesort: procedure Treesort ( var a : ArT; n : Indx ); var j : Indx; begin bld (A, n); for j := n downto 3 do begin swap (A[1], A[j]); reorg (A, 1, j-1) end end Властивість відновлюється в частині масиву A[1], … , A[n-1] таким чином. Обмінюються значення A[1] та того з A[2] або A[3] (позначимо його A[k]), чиє значення максимальне. У результаті властивість може порушитися в частині масиву A[k], … , A[n-1]. У ній відновлення відбувається так само, як і серед A[1], … , A[n-1]. Опишемо відновлення частини масиву A[i], … , A[j] у загальному випадку значень i, j.

Нехай у частині масиву A[i], … , A[j], де 2*i+1£ j, треба відновити властивість , можливо, порушену з початку: A[i]<max{A[2*i], A[2*i+1]}. За умови A[2*i]>A[2*i+1] покладемо k=2*i, у противному разі – k=2*i+1. Обміняємо значення A[i] та A[k]; після цього, якщо необхідно, властивість відновлюється в частині масиву A[k], … , A[j]. Коли 2*i=j, то лише порівнюються й, можливо, обмінюються значеннями A[i] та A[j], причому k=j. Коли 2*i>j, то властивість не може бути порушеною в частині масиву A[i], … , A[j]. За дії означень відновлення задається рекурсивною процедурою reorg: procedure reorg ( var A : ArT; i, j : Indx ); var k : Indx; begin if 2*i = j then if A[i] < A[j] then swap ( A[i], A[j] ); if 2*i < j then begin if A[2*i] > A[2*i+1] then k := 2*i else k := 2*i + 1; if A[i] < A[k] then begin swap ( A[i], A[k] ); reorg ( A, k, j ) end end end

Після виконання виклику reorg( A, i, j ) за будь-якого i<jdiv2 елемент A[i] має максимальне значення серед A[i], A[2*i], A[2*i+1]. Цим можна скористатися для побудови початкового масиву з властивістю : спочатку "відновлюється" частина масиву A[ndiv2], … , A[n], потім частина A[ndiv2-1], … , A[n] тощо. Звідси процедура bld: procedure bld (var A : ArT; n : Indx ); var i : Indx; begin for i := n div 2 downto 1 do reorg ( A, i, n ) end Оцінимо складність алгоритму.

За наведеними процедурами очевидно, що складність алгоритму прямо пропорційна загальній кількості викликів процедури reorg. При виконанні процедури bld процедура reorg викликається ndiv2 разів, а при виконанні циклу for процедури Treesort – ще n-2 рази.

Отже, загальна кількість викликів процедури reorg з інших процедур є O(n). Кількість елементарних дій при виконанні операторів її тіла оцінюється сталою, тобто O(1). У кожному рекурсивному виклику процедури reorg значення її другого параметра не менше ніж подвоюється, тому кожний виклик reorg з інших процедур породжує не більше O(logn) рекурсивних викликів. Звідси випливає, що загальна кількість елементарних дій є O(nlogn).