Пирамидальная сортировка (, «Сортировка кучей») — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за операций при сортировке элементов. Алгоритм работает «на месте» — количество задействованной служебной памяти , то есть фиксированное.
Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.
Пирамидальная сортировка была предложена в 1963 году.
Алгоритм
Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены условия:
Каждый лист имеет глубину либо , либо , — максимальная глубина дерева. Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.
Удобная структура данных для сортирующего дерева — такой массив , что - элемент в корне, а потомки элемента являются и .
Алгоритм сортировки будет состоять из двух основных шагов:
1. Выстраиваем элементы массива в виде сортирующего дерева:
при .
Этот шаг требует операций.
2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем и , преобразовываем в сортирующее дерево. Затем переставляем и , преобразовываем в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда - упорядоченная последовательность.
Этот шаг требует операций.
Достоинства и недостатки Достоинства: Имеет доказанную оценку худшего случая . Сортирует на месте, то есть требует всего дополнительной памяти (если дерево организовывать так, как показано выше).
Недостатки:
Неустойчив — для обеспечения устойчивости нужно расширять ключ. На почти отсортированных массивах работает столь же долго, как и на хаотических данных. На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти. Методу требуется доступ к произвольному элементу структуры; не работает на связанных списках и других структурах памяти последовательного доступа. Не распараллеливается.
Сортировка слиянием при расходе памяти быстрее ( с меньшей константой) и не подвержена деградации на неудачных данных.
Из-за сложности алгоритма выигрыш получается только на больших . На небольших (до нескольких тысяч) быстрее сортировка Шелла.
Применение Пирамидальная сортировка активно применяется в ядре Linux.
Примечания
Литература
Ссылки
Пирамидальная сортировка — подробное описание с иллюстрациями и примером реализации на C++. Приведён вывод оценок скорости работы алгоритма и измерение времени работы на реальной вычислительной системе. Сортировка с помощью кучи (пирамидальная сортировка) — доходчивое описание с иллюстрациями и примером реализации на Pascal. Динамическая визуализация 7 алгоритмов сортировки с открытым исходным кодом
Категория:Алгоритмы сортировки Категория:Кучи (структуры данных)