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

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

Найпоширеніша модель представлення даних для сортування — масив структур, в якому кожен елемент має поля англ. 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^** отримано нестабільним впорядкуванням.

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

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

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

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

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

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

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

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

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

Див. також

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

Джерела

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