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

Матеріал з Вікіпедії — вільної енциклопедії.

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

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

Іншими мовами