Стабильная сортировка
Стабильная сортировка — это сортировка массива, которая при одинаковых ключах сохраняет исходный порядок элементов. Это важно, когда у элементов есть несколько признаков и сортировку выполняют последовательно по ним.
Как проверяют стабильность
Чтобы различать одинаковые ключи, мысленно добавляют каждому элементу его исходный номер. Если после сортировки элементы с одним ключом идут в порядке возрастания этих номеров, сортировка стабильна. Например, при сортировке по ключу «оценка» ученики с одинаковыми оценками должны остаться в прежнем порядке.
Здесь \(k_i\) и \(k_j\) — одинаковые ключи исходных элементов, а \(i'\) и \(j'\) — их позиции после сортировки. Формула означает: если элемент \(i\) стоял раньше элемента \(j\), то после сортировки он также должен стоять раньше.
Исходный список: Анна—2, Борис—1, Вера—2. После стабильной сортировки по оценке получаем: Борис—1, Анна—2, Вера—2. Анна и Вера имеют одинаковый ключ 2, но Анна осталась перед Верой, как было исходно.
Стабильность не означает, что алгоритм обязательно работает быстрее или использует меньше памяти. Это отдельное свойство результата. Кроме того, одна и та же сортировка может быть стабильной в одной реализации и нестабильной в другой, если при равенстве элементы меняются местами.
Какой результат сохраняет порядок элементов с одинаковым ключом при стабильной сортировке?
Главное
- Стабильная сортировка сохраняет исходный относительный порядок элементов с одинаковыми ключами.
- Стабильность проверяют по номерам исходных позиций равных элементов.
- Стабильность — свойство результата и реализации, а не показатель скорости алгоритма.