Малюнок 4. Процес побудови піраміди
Отже, завдання побудови піраміди з масиву успішно вирішена. Як видно з властивостей піраміди, в корені завжди знаходиться максимальний елемент. Звідси випливає алгоритм фази 2:
· Беремо верхній елемент піраміди a [0] ... a [n] (перший в масиві) і міняємо з останнім місцями. Тепер «забуваємо» про це елементі і далі розглядаємо масив a [0] ... a [n - 1]. Для перетворення його в піраміду досить просіяти лише новий перший елемент.
· Повторюємо крок 1, поки оброблювана частина масиву не зменшиться до одного елемента.
Малюнок 5. Просіювання елементів масиву
Очевидно, що в кінець масиву щораз потрапляє максимальний елемент з поточної піраміди, тому в правій частині поступово виникає впорядкована послідовність.
Малюнок 6. Ілюстрація 2-ї фази сортування у внутрішньому поданні піраміди.
67 18 44 55 12 06 42//
55 44 06 42 18 12//94
42 44 06 12 18//67 94
42 18 червня дванадцять//55 67 94
18 грудня +06//44 55 67 94
6 грудня//42 44 55 67 94
06//18 42 44 55 67 94
//12 18 42 44 55 67 94
Побудова піраміди займає О (n log n) операцій, причому більш точна оцінка дає навіть О (n) за рахунок того, що реальний час виконання залежить від висоти вже створеної частини піраміди.
Друга фаза займає O (n log n) часу: O (n) раз береться максимум і відбувається просіювання колишнього останнього елемента. Плюсом є стабільність методу: середнє число пересилань (n log n)/2, і відхилення від цього значення порівняно малі.
Пірамідальна сортування не використовує додаткової пам'яті. Метод не є стійким: по ходу роботи масив так «перетрушується», що вихідний порядок елементів може змінитися випадковим чином, часткова впорядкованість масиву ніяк не враховується.
1.3 Паливний метод сортування
Плавне сортування - алгоритм сортування вибором, різновид пірамідальної сортування, розроблена Е. Дейкстрой в 1981 році. Як і пірамідальна сортування, має складність в гіршому випадку рівну O (n log n). Перевага плавної сортування в тому, що її складність наближається до O (n), якщо вхідні дані частково відсортовані, в той час як у пірамідальної сортування складність завжди одна, незалежно від стану вхідних даних.
Як і в пірамідальної сортуванню, в масив накопичується купа з даних, які потім сортуються шляхом безперервного видалення максимуму з купи. На відміну від пірамідальної сортування, тут використовується не двійкова купа, а спеціальна, отримана за допомогою чисел Леонардо. Купа складається з послідовності куп, розміри яких дорівнюють одному з чисел Леонардо, а коріння зберігаються в порядку зростання. Переваги таких спеціальних куп перед двійковими полягають у тому, що якщо послідовність відсортована, її створення і руйнування займе O (n) часу, що буде швидше. Розбити вхідні дані на купи просто: крайні зліва вузли масиву складуть найбільшу купу, а що залишилися будуть розділені подібним чином:
· Масив будь-якої довжини може бути також розбитий на частині розміру L (x).
· Не повинно бути двох куп однакового розміру, тому що в цьому випадку послідовність перетвориться в строго спадну за розмірами.
· Не повинно бути двох куп, розміри яких дорівнюють двом послідовним числам Леонардо, за винятком масиву довжини 2.
Ці положення можуть бути доведені:
Кожна купа розміру L (x) складається, зліва направо, з подкучі розміру L (x? 1), подкучі розміру L (x? 2) і кореня, за винятком куп розміру L (1) і L (0), які складаються тільки з кореня. Для кожної купи виконується наступна властивість: значення кореня повинно бути не менше значень коренів його куп-нащадків (і, як наслідок, не менше значень всіх вузлів його куп-нащадків). Для послідовності куп в свою чергу виконується наступна властивість: значення кореня кожної купи повинно бути не менше значення кореня купи зліва. Наслідок цього - крайній правий вузол в послідовності матиме найбільше значення, і, що важливо, частково відсортований масив не потребуватиме перестановці елементів, для того щоб стати правильної послідовністю куп. Це є джерелом пристосовності алгоритму. Алгоритм простий. Спочатку відбувається поділ відсортованого масиву на купу з одним елементом і невідсортовану частину. Купа з одним елементом, очевидно, являє собою правильну послідовність куп. Послідовність починає рости шляхом додавання по одному елементу праворуч за раз (якщо ...
