Что такое стабильность сортировки и когда она важна?
Постоянно встречаю «стабильная сортировка» / «нестабильная». Что это значит на практике и в каких случаях разница реально вылезет? И стабильна ли встроенная сортировка в Python?
3 ответа
Сортировка стабильная, если элементы с одинаковым ключом сохраняют свой исходный относительный порядок. Это важно при сортировке по нескольким критериям подряд.
Пример: список людей, отсортированный по имени. Если потом стабильно отсортировать его по возрасту, то люди одного возраста останутся упорядочены по имени — получишь сортировку «по возрасту, потом по имени» бесплатно.
people = [('Аня', 30), ('Боря', 25), ('Вера', 30), ('Глеб', 25)]
people.sort(key=lambda p: p[0]) # по имени
people.sort(key=lambda p: p[1]) # по возрасту, стабильно
# [('Боря',25),('Глеб',25),('Аня',30),('Вера',30)]
В Python и sorted(), и list.sort() гарантированно стабильны (под капотом Timsort).
Стабильная = равные ключи не перемешиваются. В Python sorted и .sort стабильны, можно смело сортировать в несколько проходов.
Да, стабильна.
