Стійка (стабільна) сортування - сортування, яка не змінює відносний порядок сортируемих елементів, що мають однакові ключі.
Стійкість є дуже важливою характеристикою алгоритму сортування, але, тим не менш, вона практично завжди може бути досягнута шляхом подовження вихідних ключів за рахунок додаткової інформації про їх первісному порядку. Незважаючи на гадану необхідність, що випливає з назви, стійкість зовсім не обов'язкова для правильності сортування і найчастіше не дотримується, так як для її забезпечення практично завжди необхідні додаткова пам'ять і час.
При сортуванні записів виду [прізвище, ім'я, по батькові] на прізвище значення ключів для Іванов Сергій і Іванов Іван будуть однакові, тому стійка сортування не перестаючи Сергія і Івана місцями (Python 3. сортування timsort [1]):
В результаті записи будуть відсортовані тільки на прізвище, зі збереженням вихідного порядку серед записів з однаковими прізвищами:
Сортування, яка є основним витратним елементом перетворення Барроуза - Уиллера. повинна бути стійкою.
Алгоритми стійкою сортування
Сортування злиттям з додатковою пам'яттю
При цьому алгоритмі сортування спочатку здійснюється рекурсивне поділ вихідного масиву на частини доти, поки в кожній частині масиву не виявиться один або нуль елементів (на кожному кроці рекурсії здійснюється поділ навпіл). Після цього отримані частини попарно «зливаються». Загальна складність алгоритму - O (n log n), при цьому алгоритму потрібно O (n) додаткової пам'яті для зберігання злитих масивів.
Сортування з використанням стійкого поділу
Даний алгоритм схожий на алгоритм швидкого сортування. Так само як і в алгоритмі швидкого сортування, в даному алгоритмі вихідний масив поділяється на дві частини - в одній всі елементи менше або дорівнюють деякого опорного елементу, а в іншій - більше або рівні. Після цього розділені частини масиву рекурсивно упорядковано таким же чином. Відмінність цього алгоритму від алгоритму швидкого сортування в тому, що тут використовується сталий поділ замість нестійкого. Нижче приведена реалізація даного алгоритму на псевдокоді:
Для стійкого поділу масиву потрібно O (n log n) елементарних операцій. Так як «глибина» здійснюваного рекурсивного спуску в середньому випадку становить O (log n) то загальна складність алгоритму становить O (n log² n). При цьому алгоритму для здійснення рекурсії буде потрібно O (log n) стековой пам'яті, хоча в гіршому випадку загальна складність дорівнює O (n ² log n) і потрібно O (n) пам'яті.
Алгоритми сортування злиттям без додаткової пам'яті
Всі описані нижче алгоритми засновані на злитті вже відсортованих масивів без використання додаткової пам'яті понад O (log² n) стековой пам'яті (це - т. Зв. Умова мінімальної пам'яті [2]) і відрізняються лише алгоритмом злиття. Далі наведено псевдокод алгоритмів (алгоритми злиття - процедура Merge - наводяться окремо для кожного методу):
алгоритм Пратта
В алгоритмі Пратта в відсортованих масивах знаходять два елементи α і β. які є медианами масиву, що складається з елементів обох масивів. Тоді весь масив можна представити у вигляді aαbxβy. Після цього здійснюється циклічний зсув елементів, в результаті чого отримуємо таку послідовність: axβαby. Далі алгоритм злиття рекурсивно повторяться для масивів ax і by.
Циклічний зсув елементів вимагає O (n) елементарних операцій і O (1) додаткової пам'яті, а пошук медіан в двох вже відсортованих масивах - O (log² n) елементарних операцій і O (1) додаткової пам'яті. Так як здійснюється O (log n) кроків рекурсії, то складність такого алгоритму злиття становить O (n log n), а загальна складність алгоритму сортування - O (n log² n). При цьому алгоритму потрібно O (log² n) стековой пам'яті.
Алгоритм без пошуку медіан
Від пошуку медіан в попередньому алгоритмі можна позбутися в такий спосіб. У більшому з двох масивів вибираємо середній елемент α (опорний елемент). Далі в меншому масиві знаходимо позицію першого входження елемента більшого або рівного α. Назвемо його β. Після цього здійснюється циклічний зсув елементів так само як і в алгоритмі Пратта (aαbxβy → axβαby) і здійснюється рекурсивне злиття отриманих частин. Псевдокод алгоритму злиття наведено нижче.
Процедури FindFirstPosition і FindLastPosition практично збігаються з процедурою довічного пошуку:
На відміну від алгоритму Пратта, в даному алгоритмі розбиття може бути істотно нерівним. Але навіть в гіршому випадку алгоритм розіб'є весь діапазон [a. y] у співвідношенні 3: 1 (якщо всі елементи другого діапазону будуть більше або менше опорного і при цьому обидва діапазону мають рівне число елементів). Це гарантує логарифмічна число кроків рекурсії при злитті будь-яких масивів. Таким чином отримуємо, що так само, як і в алгоритмі Пратта, складність алгоритму злиття дорівнює O (n log n), складність алгоритму сортування - O (n log² n), а необхідна пам'ять - O (log² n).
Стійка сортування без додаткової пам'яті за час O (n log n)
Шляхи поліпшення алгоритмів
- У всіх вищенаведених алгоритмах при розбитті вихідного масиву на частини рекурсивне розбиття можна зупинити, якщо розмір разбиваемого масиву стане досить маленьким. Тоді можна застосувати будь-якої з простих алгоритмів сортування (наприклад, сортування вставками), які, як відомо, працюють швидше ніж складні, якщо розмір вхідного масиву невеликий. Фактично даний прийом можна застосувати не тільки для представлених тут алгоритмів, але і для будь-якого іншого алгоритму, де застосовується рекурсивне розбиття вихідного масиву (наприклад, звичайна нестабільна швидке сортування). Конкретне число вхідних елементів, при якому треба переходити на простий алгоритм сортування, залежить від використовуваної обчислювальної машини.
- В алгоритмі Пратта, алгоритмі без пошуку медіан і алгоритмі з використанням стійкого поділу замість того, щоб кожен раз рекурсивно викликати процедуру злиття, можна динамічно виділити масив тимчасових змінних. Тоді можна буде продовжувати розбиття діапазону лише до тих пір, поки число елементів в більшому діапазоні не стане менше або дорівнює місткості тимчасового масиву. Фактично на певному етапі рекурсії алгоритм Пратта і алгоритм без пошуку медіан перетворюються в алгоритм простого злиття. Т. о. якщо в системі досить динамічної пам'яті, то асимптотическое час роботи можна довести до O (n log n) замість O (n log² n).