Відкрити головне меню

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

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

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

За час  

За час  

За час   з використанням додаткової інформації про елементи

За час  

Див. такожРедагувати

ДжерелаРедагувати

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