Меню Главная Случайная статья Настройки Пирамидальная сортировка Материал из https://ru.wikipedia.org Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»[1]) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за ${\displaystyle O(n\log n)}$ операций при сортировке ${\displaystyle n}$ элементов.[2] Алгоритм работает «на месте» — количество задействованной служебной памяти ${\displaystyle O(1)}$, то есть фиксированное[1]. Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям. Пирамидальная сортировка была предложена Дж. Уильямсом[англ.] в 1963 году.[1] Содержание 1 Алгоритм 2 Достоинства и недостатки 3 Применение 4 Примечания 5 Литература 6 Ссылки Алгоритм Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены условия: Каждый лист имеет глубину либо ${\displaystyle d}$, либо ${\displaystyle d-1}$, ${\displaystyle d}$ — максимальная глубина дерева. Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков. Удобная структура данных для сортирующего дерева — такой массив ${\displaystyle a}$, что ${\displaystyle a[0]}$ - элемент в корне, а потомки элемента ${\displaystyle a[i]}$ являются ${\displaystyle a[2i+1]}$ и ${\displaystyle a[2i+2]}$. Алгоритм сортировки будет состоять из двух основных шагов: 1. Выстраиваем элементы массива в виде сортирующего дерева[источник не указан 3265 дней]: ${\displaystyle a[i]\geq a[2i+1]}$ ${\displaystyle a[i]\geq a[2i+2]}$ при ${\displaystyle 0\leq i<n/2}$. Этот шаг требует ${\displaystyle O(n\log n)}$ операций. 2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем ${\displaystyle a[0]}$ и ${\displaystyle a[n-1]}$, преобразовываем ${\displaystyle a[0],a[1],\ ...,a[n-2]}$ в сортирующее дерево. Затем переставляем ${\displaystyle a[0]}$ и ${\displaystyle a[n-2]}$, преобразовываем ${\displaystyle a[0],a[1],\ ...,a[n-3]}$ в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда ${\displaystyle a[0],a[1],\ ...,a[n-1]}$ - упорядоченная последовательность. Этот шаг требует ${\displaystyle O(n\log n)}$ операций. Достоинства и недостатки Достоинства: Имеет доказанную оценку худшего случая ${\displaystyle O(n\log n)}$. Сортирует на месте, то есть требует всего ${\displaystyle O(1)}$ дополнительной памяти (если дерево организовывать так, как показано выше). Недостатки: Неустойчив — для обеспечения устойчивости нужно расширять ключ. На почти отсортированных массивах работает столь же долго, как и на хаотических данных. На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти[1]. Методу требуется доступ к произвольному элементу структуры; не работает на связанных списках и других структурах памяти последовательного доступа. Не распараллеливается. Сортировка слиянием при расходе памяти ${\displaystyle O(n)}$ быстрее (${\displaystyle O(n\log n)}$ с меньшей константой) и не подвержена деградации на неудачных данных. Из-за сложности алгоритма выигрыш получается только на больших ${\displaystyle n}$. На небольших ${\displaystyle n}$ (до нескольких тысяч) быстрее сортировка Шелла. Применение Пирамидальная сортировка активно применяется в ядре Linux[3]. Примечания 1 2 3 4 Курс лекций «Современные технологии параллельного программирования», Лекция № 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. Ссылки Пирамидальная сортировка — подробное описание с иллюстрациями и примером реализации на C++. Приведён вывод оценок скорости работы алгоритма и измерение времени работы на реальной вычислительной системе. Сортировка с помощью кучи (пирамидальная сортировка) — доходчивое описание с иллюстрациями и примером реализации на Pascal. Динамическая визуализация 7 алгоритмов сортировки с открытым исходным кодом Архивная копия от 20 сентября 2017 на Wayback Machine