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

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

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

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