Пирамидальная сортировка

Анимированная схема алгоритма

Пирамидальная сортировка (Шаблон:Lang-en, «Сортировка кучей») — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за $O(n\log n)$ операций при сортировке $n$ элементов. Алгоритм работает «на месте» — количество задействованной служебной памяти $O(1)$, то есть фиксированное.

Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.

Пирамидальная сортировка была предложена Шаблон:Iw в 1963 году.

Алгоритм

Пример сортирующего дерева

структура хранения данных сортирующего дерева

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

1. Каждый лист имеет глубину либо $d$, либо $d-1$, $d$ — максимальная глубина дерева.
2. Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.

Удобная структура данных для сортирующего дерева — такой массив $a$, что $a[0]$ - элемент в корне, а потомки элемента $a[i]$ являются $a[2i+1]$ и $a[2i+2]$.

Алгоритм сортировки будет состоять из двух основных шагов:

1. Выстраиваем элементы массива в виде сортирующего дереваШаблон:Нет АИ:

$a[i]\ge a[2i+1]$

$a[i]\ge a[2i+2]$

при $0\le i<n/2$.

Этот шаг требует $O(n\log n)$ операций.

2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем $a[0]$ и $a[n-1]$, преобразовываем $a[0],a[1],...,a[n-2]$ в сортирующее дерево. Затем переставляем $a[0]$ и $a[n-2]$, преобразовываем $a[0],a[1],...,a[n-3]$ в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда $a[0],a[1],...,a[n-1]$ - упорядоченная последовательность.

Этот шаг требует $O(n\log n)$ операций.

Достоинства и недостатки

Достоинства:

• Имеет доказанную оценку худшего случая $O(n\log n)$.
• Сортирует на месте, то есть требует всего $O(1)$ дополнительной памяти (если дерево организовывать так, как показано выше).

Недостатки:

• Неустойчив — для обеспечения устойчивости нужно расширять ключ.
• На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
• На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.
• Методу требуется доступ к произвольному элементу структуры; не работает на связанных списках и других структурах памяти последовательного доступа.
• Не распараллеливается.

Сортировка слиянием при расходе памяти $O(n)$ быстрее ($O(n\log n)$ с меньшей константой) и не подвержена деградации на неудачных данных.

Из-за сложности алгоритма выигрыш получается только на больших $n$. На небольших $n$ (до нескольких тысяч) быстрее сортировка Шелла.

Применение

Пирамидальная сортировка активно применяется в ядре Linux.

Литература

• Шаблон:Source
• Шаблон:Книга:CLRS

Ссылки

• Пирамидальная сортировка — подробное описание с иллюстрациями и примером реализации на C++. Приведён вывод оценок скорости работы алгоритма и измерение времени работы на реальной вычислительной системе.
• Сортировка с помощью кучи (пирамидальная сортировка) — доходчивое описание с иллюстрациями и примером реализации на Pascal.
• Динамическая визуализация 7 алгоритмов сортировки с открытым исходным кодом Шаблон:Wayback