Информатика · объяснение и практика

Что сохраняет стабильная сортировка одинаковых ключей

Что означает стабильность сортировки, какой порядок сохраняется при равных ключах и как различаются sorted и изменение списка на месте в Python.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Электронные таблицы и форматы данных · Учебная карта

Главная мысль

Стабильная сортировка сохраняет исходный взаимный порядок элементов с равными ключами. Она не делает такие элементы автоматически алфавитными или одинаковыми. Сначала укажите ключ сравнения, затем выясните, какой дополнительный порядок уже существовал и должен сохраниться внутри равных групп.

Какие элементы считаются равными для сортировки

Имеются записи «Ира — два балла», «Лев — один балл», «Оля — два балла» именно в таком исходном порядке. При сортировке по числу баллов по возрастанию первым станет Лев. Ира и Оля имеют одинаковый ключ два, поэтому стабильный алгоритм оставит Иру перед Олей. Сами записи различаются именами, но равенство ключей определяется выбранным полем баллов.

Если начать с другого исходного порядка равных ключей, стабильный результат тоже будет другим внутри этой группы. Поэтому стабильность не означает дополнительную скрытую сортировку по имени. Для требования «сначала балл, затем имя» нужно явно задать составной ключ или заранее выстроить нужный вторичный порядок. Алгоритм сохраняет то, что было, а не угадывает желаемое правило.

Как это используется в нескольких проходах

Можно сначала отсортировать записи по вторичному признаку, затем стабильно по основному. Внутри одинаковых основных ключей сохранится ранее созданный вторичный порядок. Такой приём работает именно благодаря стабильности. Но порядок двух проходов существенен: последний проход задаёт главную группировку, а не первый. Перестановка этапов меняет смысл результата.

В Python функции sorted и метод списка sort являются стабильными. sorted создаёт новый отсортированный список, не переставляя исходный список на месте. Метод sort изменяет сам список и возвращает None. Поэтому запись items = items.sort() не сохраняет в имени отсортированный список: после выполнения имя получит None, хотя прежний объект списка уже был изменён.

Пример

Исходно: Ира — 2, Лев — 1, Оля — 2. По баллам стабильно: Лев — 1, Ира — 2, Оля — 2.

Ира и Оля сохранили взаимный порядок, потому что их ключи одинаковы. Отдельного алфавитного критерия в условии нет.

Как проверить, что обещание действительно выполнено

Для теста пометьте элементы равных ключей разными метками и запомните их исходный порядок. После сортировки проверьте две вещи: ключи идут правильно, а метки внутри каждой равной группы сохранили порядок. Один тест без повторяющихся ключей не проверяет стабильность вообще. В нём любая перестановка равных элементов просто невозможна, поэтому важное свойство остаётся невидимым.

Разворот уже отсортированного списка целиком переворачивает и порядок внутри равных групп. Это не то же самое, что стабильная сортировка по убыванию с сохранением порядка равных ключей. При необходимости обратного направления используйте подходящий режим сортировки, а не автоматически заменяйте его разворотом готового результата. Семантика равных элементов должна оставаться согласованной с задачей.

Правило сравнения тоже задаётся явно. Строковые имена могут требовать языкового порядка, который отличается от простого порядка кодовых точек. Стабильность сама по себе не решает вопросы регистра, буквы ё или культурной сортировки. Это свойства ключа и механизма сравнения. Отделение этих задач помогает не обещать пользователю больше, чем гарантирует конкретная операция.

От чтения к действию

А теперь — вы

При стабильной сортировке по баллам две записи имеют одинаковый балл. Что сохраняется?

Частые вопросы

Стабильная сортировка расставит равные баллы по алфавиту?

Только если такой вторичный порядок уже был создан или явно задан ключом. Стабильность сама сохраняет исходное положение равных ключей.

Почему нужно проверять элементы с одинаковым ключом?

Именно для них определяется стабильность. Без повторяющихся ключей тест не способен отличить стабильный алгоритм от нестабильного.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться