PROFILPELAJAR.COM

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

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

Пирамидальная сортировка была предложена Дж. Уильямсом^[англ.] в 1963 году.^[1]

Алгоритм

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

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

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

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

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

1. Выстраиваем элементы массива в виде сортирующего дерева^{[источник не указан 3015 дней]}:

a[i]\geq a[2i+1]

a[i]\geq a[2i+2]

при

0\leq i<n/2

.

Этот шаг требует

O(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)$ дополнительной памяти (если дерево организовывать так, как показано выше).

Недостатки:

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

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

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

Применение

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

Примечания

↑ ¹ ² ³ ⁴ Курс лекций «Современные технологии параллельного программирования», Лекция № 5: Пирамидальная сортировка (неопр.). Дата обращения: 20 марта 2009. Архивировано из оригинала 15 марта 2009 года.
↑ ScienceDirect — Journal of Algorithms : The Analysis of Heapsort (неопр.). Дата обращения: 30 сентября 2017. Архивировано 4 июня 2012 года.
↑ sort.c « lib - kernel/git/torvalds/linux.git - Linux kernel source tree (неопр.). git.kernel.org. Дата обращения: 7 июля 2023. Архивировано 7 июля 2023 года.

Литература

Левитин А. В. Глава 6. Метод преобразования: Пирамиды и пирамидальная сортировка // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 275—284. — 576 с. — ISBN 978-5-8459-0987-9
Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 6. Пирамидальная сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 182—188. — ISBN 5-8459-0857-4.