Плавне сортування

Плавне сортування (англ. 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. Крайня права купа (сформована останньою) вважається «поточної» купою.
2. Поки зліва від неї є купа і значення її кореня більше значення поточного кореня і обох коренів куп-нащадків:
   • Міняються місцями новий корінь і корінь купи зліва (що не порушить властивість для поточної купи). Ця купа стає поточною.
3. Виконується «просіювання», щоб виконувати властивість купи:
   • Поки розмір поточної купи більше 1 і значення кореня будь-якого з куп-нащадків більше значення кореня поточної купи:
     • Міняються місцями найбільший за значенням корінь купи-нащадка і поточний корінь. Купа-нащадок стає поточної купою.

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

Оптимізація

• Якщо очікується, що нова купа стане частиною поточної, до моменту закінчення, не потрібно перевіряти виконання властивості купи: це знадобиться тільки в разі, якщо купа досягне кінцевого стану.
  • Для цього потрібно поглянути на кількість ,що залишилася після формування купи розміру L (x) елементів. Якщо вона більша, ніж L (x - 1) + 1, тоді ця нова купа буде поглинена.
• Необов'язково дотримуватися виконання властивості купи для крайньої правої купи. Якщо ця купа стане однією з кінцевих куп послідовності куп, то виконання властивості послідовності куп забезпечить виконання властивості купи. Звичайно, всякий раз коли формується нова купа, крайня права купа не стає крайньою правою, і виконання властивості купи повинно бути відновлено.

Зменшення послідовності куп шляхом видалення елемента праворуч

Якщо розмір крайньої правої купи дорівнює 1 - тобто це купа L (1) або L (0), - то ця купа просто видаляється. В іншому випадку корінь цієї купи видаляється, купи-нащадки вважаються елементами послідовності куп, після чого перевіряється виконання властивості купи, спочатку для лівої купи, потім - для правої.

Оптимізація

• Значення кореня купи зліва і значення вузлів куп, які тільки що утворилися з куп-нащадків,не порівнюються, так як відомо, що властивість для них виконується. Тому порівняння відбувається тільки зі значенням кореня.

Використовувана пам'ять

Алгоритм плавного сортування вимагає пам'яті для зберігання розмірів всіх куп в послідовності. Так як всі ці значення різні, як правило, для цієї мети застосовується бітова карта. Крім того, так як в послідовності не більш ніж O (log n) чисел, біти можуть бути закодовані О (1) машинними словами .

Джерела

• Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — .(англ.)
• Оригінальна стаття (англ.)
• Оригінальна стаття з коментарями (англ.)
• Дослідження алгоритму (К. Schwarz) (англ.)