Плавне сортування
Плавне сортування (англ. Smoothsort) — алгоритм сортування, різновид пірамідального сортування, розроблений Е. Дейкстрою 1981 року. Як і пірамідальне сортування, в найгіршому випадку має швидкодію О(n log n). Перевагою плавного сортування є те, що його швидкодія наближається до O(n), якщо вхідні дані частково відсортовано, в той час як швидкодія пірамідального сортування є незмінною та не залежить від стану вхідних даних.
 Плавне сортування оперує на майже відсортованому масиві. Лінії зверху показують структуру дерева. | |
| Клас | Алгоритм сортування |
|---|---|
| Структура даних | Масив |
| Найгірша швидкодія | O(n log n) |
| Найкраща швидкодія | O(n) |
| Середня швидкодія | O(n log n) |
Огляд алгоритму
Як і в пірамідальному сортуванні, до масиву накопичується купа з даних, які потім сортуються шляхом безперервного видалення максимуму з купи. На відміну від пірамідального сортування, тут використовується не двійкова купа, а спеціальна, отримана за допомогою чисел Леонардо. Купа складається з послідовності куп, розміри яких дорівнюють одному з чисел Леонардо, а корені зберігаються в порядку зростання. Переваги таких спеціальних куп перед двійковими полягають у тім, що якщо послідовність відсортовано, то її створення й руйнування займе O(n) часу, що буде швидше. Розбити вхідні дані на купи просто: крайні ліворуч вузли масиву складуть найбільшу можливу купу, а решту буде розділено подібним чином.
Можливо довести, що:
- Масив будь-якої довжини може бути також розбито на частини розміру L(x).
- Не повинно бути двох куп однакового розміру, оскільки в цьому випадку послідовність перетвориться на строго спадну за розмірами.
- Не повинно бути двох куп, розміри яких дорівнюють двом послідовним числам Леонардо, за винятком масиву з довжиною 2.
Операції
Збільшення послідовності куп шляхом додавання елемента
- Якщо дві останні купи мають розміри L (x + 1) і L (x) (двох послідовних чисел Леонардо), новий елемент стає коренем купи більшого розміру, рівного L (x + 2). Для неї властивість купи необов'язкова.
- Якщо розміри двох останніх куп не дорівнюють двом послідовним числам Леонардо, новий елемент утворює нову купу розміром 1. Цей розмір вважається рівним L (1), крім випадку, коли крайня права купа вже має розмір L (1), тоді розмір нової одноелементної купи вважають рівним L (0).
Після цього має бути відновлено виконання властивостей купи і послідовності куп, яке, як правило, досягається за допомогою різновиду сортування вставками:
- Крайня права купа (сформована останньою) вважається «поточної» купою.
- Поки зліва від неї є купа і значення її кореня більше значення поточного кореня і обох коренів куп-нащадків:
- Міняються місцями новий корінь і корінь купи зліва (що не порушить властивість для поточної купи). Ця купа стає поточною.
- Виконується «просіювання», щоб виконувати властивість купи:
- Поки розмір поточної купи більше 1 і значення кореня будь-якого з куп-нащадків більше значення кореня поточної купи:
- Міняються місцями найбільший за значенням корінь купи-нащадка і поточний корінь. Купа-нащадок стає поточної купою.
- Поки розмір поточної купи більше 1 і значення кореня будь-якого з куп-нащадків більше значення кореня поточної купи:
Операція просіювання значно спрощена завдяки використанню цифр Леонардо, так як кожна купа або буде одноелементною, або буде мати двох нащадків. Нема потреби турбуватися про відсутність однієї з куп-нащадків.
Оптимізація
- Якщо очікується, що нова купа стане частиною поточної, до моменту закінчення, не потрібно перевіряти виконання властивості купи: це знадобиться тільки в разі, якщо купа досягне кінцевого стану.
- Для цього потрібно поглянути на кількість ,що залишилася після формування купи розміру L (x) елементів. Якщо вона більша, ніж L (x - 1) + 1, тоді ця нова купа буде поглинена.
- Необов'язково дотримуватися виконання властивості купи для крайньої правої купи. Якщо ця купа стане однією з кінцевих куп послідовності куп, то виконання властивості послідовності куп забезпечить виконання властивості купи. Звичайно, всякий раз коли формується нова купа, крайня права купа не стає крайньою правою, і виконання властивості купи повинно бути відновлено.
Зменшення послідовності куп шляхом видалення елемента праворуч
Якщо розмір крайньої правої купи дорівнює 1 - тобто це купа L (1) або L (0), - то ця купа просто видаляється. В іншому випадку корінь цієї купи видаляється, купи-нащадки вважаються елементами послідовності куп, після чого перевіряється виконання властивості купи, спочатку для лівої купи, потім - для правої.
Оптимізація
- Значення кореня купи зліва і значення вузлів куп, які тільки що утворилися з куп-нащадків,не порівнюються, так як відомо, що властивість для них виконується. Тому порівняння відбувається тільки зі значенням кореня.
Використовувана пам'ять
Алгоритм плавного сортування вимагає пам'яті для зберігання розмірів всіх куп в послідовності. Так як всі ці значення різні, як правило, для цієї мети застосовується бітова карта. Крім того, так як в послідовності не більш ніж O (log n) чисел, біти можуть бути закодовані О (1) машинними словами .
Посилання
- Оригінальна стаття (англ.)
- Оригінальна стаття з коментарями (англ.)
- Дослідження алгоритму (К. Schwarz) (англ.)