Кратко и по делу.
Что такое стабильная сортировка
- Стабильная сортировка сохраняет относительный порядок равных элементов: если в исходном массиве элемент A идёт перед B и их ключи равны, то в отсортированном массиве A останется перед B. Формально: если для индексов $i<j$ выполнено $\text{key}(A[i])=\text{key}(A[j])$, то после сортировки позиция $i$ останется меньше позиции $j$.
В каких задачах это важно
- Многоступенчатая (мультиключевая) сортировка: сначала по младшему ключу, затем стабильной сортировкой по старшему — даст корректный итоговый порядок (пример: сортировка по фамилии и имени).
- Базы данных и отчёты: сохранение первоначального порядка при равных значениях (например, временная метка).
- UI/интерфейсы: при одинаковом приоритете элементы не «прыгают» местами.
- Комбинация алгоритмов (radix sort: LSD-метод требует стабильной сортировки по разрядам).
- Внешняя сортировка и слияние потоков — стабильность упрощает объединение.
Реализация стабильной сортировки за $\mathcal{O}(n\log n)$
1) Merge sort (простая, гарантированно стабильная)
- Идея: рекурсивно разбить массив на две половины, отсортировать и слить.
- Ключевой момент стабильности при слиянии: при равных ключах выбирать элемент из левой части первым.
Псевдокод (описание):
- merge(left, right):
- i = 0; j = 0; out = []
- пока $i<|left|$ и $j<|right|$:
- если $\text{key}(left[i])\le \text{key}(right[j])$ — append left[i]; $i\leftarrow i+1$ - иначе — append right[j]; $j\leftarrow j+1$ - добавить остатки
- mergesort(A): рекурсивно разделить, отсортировать половины и вызвать merge.
Анализ:
- Время: $\mathcal{O}(n\log n)$ в худшем, среднем и лучшем случае.
- Доп. память: обычно $\mathcal{O}(n)$ для временного буфера (поддержание стабильности простое и надёжное).
- Простая, надёжная и широко используемая реализация стабильной сортировки.
2) Адаптация quicksort для стабильности (с дополнительной памятью)
- Классический in-place quicksort неустойчив. Можно сделать стабильную версию, используя временные списки при разделении, сохраняя порядок элементов.
Псевдокод:
- stable_quicksort(A):
- если $|A|\le 1$ — вернуть A
- выбрать опорный элемент $p$ (лучше случайно для среднекого поведения)
- L = []; E = []; G = []
- для каждого x в A:
- если $\text{key}(x)<\text{key}(p)$ — append x в L
- иначе если $\text{key}(x)=\text{key}(p)$ — append x в E
- иначе — append x в G
- вернуть stable_quicksort(L) + E + stable_quicksort(G)
Анализ:
- Стабильность: сохранение порядка внутри L, E, G обеспечивает глобальную стабильность.
- Время: в среднем $\mathcal{O}(n\log n)$ при хорошем выборе опорного элемента (например, случайный); в худшем $\mathcal{O}(n^2)$ (если плохо выбирать опор).
- Память: требуется дополнительное пространство, обычно $\mathcal{O}(n)$ (создаются вспомогательные списки).
Замечания и рекомендации
- Если нужна гарантия $\mathcal{O}(n\log n)$ в худшем случае и стабильность — выбирать merge sort.
- Если важна средняя скорость и допустимая доп. память — стабильный quicksort с рандомизацией может подойти.
- In-place стабильная сортировка с временем $\mathcal{O}(n\log n)$ и $\mathcal{O}(1)$ доп. памяти возможна, но сложна и редко используется на практике.
Если надо, могу дать конкретную реализацию (код) merge sort или стабильного quicksort на выбранном языке.