Стабільне сортування

Стабільним (або стійким) називається такий алгоритм сортування, що не змінює порядок елементів з однаковим ключем.

Найпоширеніша модель представлення даних для сортування — масив структур, в якому кожен елемент має поля англ. key (ключ по якому відбувається впорядкування) і їх значення англ. data (інша інформація).

Приклад

Масив прізвищ (дані) і років народження (ключі):

A = {(1988, «Знов'як»), (1984, «Олефіренко»), (1972, «Кордубан»), (1984, «Ткачук»)}

Якщо впорядкувати масив A за ключем, то можна отримати два різні результати:

A^* = {(1972, «Кордубан»), (1984, «Олефіренко»), (1984, «Ткачук»), (1988, «Знов'як»)}

A^** = {(1972, «Кордубан»), (1984, «Ткачук»), (1984, «Олефіренко»), (1988, «Знов'як»)}

Масиви A^* і A^** відрізняються порядком розташування елементів (1984, «Олефіренко») і (1984, «Ткачук») (хоча обидва масиви є впорядкованими за ключем). В A^* порядок елементів з однаковими ключами такий же як і в початковому масиві A, натомість в масиві A^** цей порядок змінено. Масив A^* отримано стабільним впорядкуванням, тоді як масив A^** отримано нестабільним впорядкуванням.

Алгоритми стабільного впорядкування

За час ${\displaystyle \;O(n^{2})}$

• (сортування вставкою)
• (сортування обміном)

За час ${\displaystyle O(n\log \;n)}$

• (сортування злиттям)

За час ${\displaystyle \;O(n)}$ з використанням додаткової інформації про елементи

• (сортування підрахунком)
• (сортування за розрядами)
• (сортування комірками)

За час ${\displaystyle O(n\log ^{2}\;n)}$

• (сортування злиттям модифіковане)

Див. також

• Алгоритм сортування
• Нотація Ландау — нотація «велике О».

Джерела

• Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press.