Цей алгоритм використовує таку структуру даних, яка власне і називається купа. Купа являє собою бінарне дерево, для якого виконується умова, що кожен лист дерева, тобто вузол без нащадків, має глибину d або d-1, де d — це глибина дерева.

На прикладі такої купи ми й розглянемо алгоритм. Основний принцип цього алгоритму ґрунтується на побудові та зміні бінарного дерева таким чином, щоб у його корені завжди знаходилося максимальне значення.

Отже, почнемо. Будемо слідкувати за алгоритмом крок за кроком.

Крок 1

Для початку розберемося, яким чином отримати бінарне дерево зі звичайного несортованого масиву. Тут все досить просто: починаючи з нульового елементу послідовно заповнюємо рівні дерева зліва направо, як показано на малюнку нижче. Виходить, що корень дерева — це нульовий елемент масиву, його нащадки — це перший і другий елемент і, відповідно, нащадки лівої гілки — це 3 і 4 елемент, а правої — 5 і 6 і так далі.

Крок 2

Відтак, нам потрібно перетворити це дерево таким чином, щоб у корені дерева знаходився максимальний елемент, а значення у кожному вузлі було більшим, ніж значення в його нащадках. Для цього ми дивимся на передостанній рівень дерева і для кожного вузла перевіряємо, чи виконується умова: кожен нащадок має бути менший за свого батька. Якщо ні, то знаходимо максимальний елемент серед нащадків і міняємо його місцями з батьківським. Проходимо таким чином кожним рівнем дерева знизу вгору і в результаті ми отримаємо сортувальне дерево, в корені якого знаходиться максимальне число. Перетворене дерево виглядатиме ось так: Може виникнути питання, куди зник масив? Гарне питання. Масив — це і є дерево. Всі перестановки, які ми нібито робимо в дереві — це переставляння елементів у масиві. Відповідність індексів масиву і вузлів було вказано на першому малюнку. По суті, ми поміняли місцями 1 <—> 4 елемент масиву і 2 <—> 6.

Масив на цьому кроці виглядає [9, 8, 4, 7, 3, 1, 2].

Крок 3

Тепер ми поміняємо місцями нульовий і останній елемент масиву і «відріжемо» гілку з максимальним елементом.

Масив тепер виглядає так: [2, 8, 4, 7, 3, 1, 9].

Крок 4

Все, що потрібно робити далі — це схожим чином привести дерево до такого вигляду, щоб виконувалась зазначена вище умова: кожен нащадок має бути менше свого батька. Дії схожі, тільки тепер ідемо зверху вниз і переставляємо елементи там, де умова порушується. На другій ітерації дерево виглядатиме наступним чином:

Знову у нас максимальний елемент в корені, і ми міняємо його місцями з передостаннім елементом масиву, так як останній елемент і так є максимальним серед усіх. «Відрізаємо» від дерева гілку з максимальним елементом. Масив матиме наступний вигляд: [1, 7, 4, 2, 3, 8, 9].

Таким чином, в кінці масиву ми складаємо вже відсортовані елементи. Ітерації виконуються до тих пір, поки масив не буде повністю відсортовано, і все листя з дерева не буде зрізане.

А тепер головне питання: для чого це все робилося? Пірамідальний алгоритм відрізняється чудовою обчислювальною складністю і не потребує додаткової пам’яті. Доведена оцінка складності у гіршому випадку O(n log n), що є дуже добре. При цьому потрібно всього O(1) пам’яті (тобто, буфер для виконання перестановок). Однак в деяких реалізаціях можна обійтися і без нього.

Втім, у кожній бочці меду є ложка дьогтю.

1. Це сортування нестійке. Про це треба пам’ятати, якщо порядок однакових елементів у масиві важливий.
2. На майже відсортованих масивах такий алгоритм працюватиме так само довго, як і на випадкових. Алгоритм не розпаралелюється і може бути реалізований тільки на структурах, які аналогічні масиву, де є прямий доступ до елементів за індексом. На пов’язаних списках такий алгоритм реалізувати не вдасться.
3. Алгоритм буде ефективнішим на великих обсягах даних. Якщо даних небагато — сортування Шелла його обжене.

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

Ще більше сортувань ви знайдете тут:

• Розбираємо сортування Шелла.
• Розбираємо прості сортування. Бульбашкове сортування.
• Розбираємо прості сортування на прикладах.