Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




13.01.2022


29.12.2021


09.12.2021


09.12.2021


08.11.2021





Яндекс.Метрика





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

14.01.2022

Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей») — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за O ( n log ⁡ n ) {displaystyle O(nlog n)} операций при сортировке n {displaystyle n} элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O ( 1 ) {displaystyle O(1)} ).

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

История создания

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

Алгоритм

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

  • Каждый лист имеет глубину либо d {displaystyle d} , либо d − 1 {displaystyle d-1} , d {displaystyle d} — максимальная глубина дерева.
  • Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.
  • Удобная структура данных для сортирующего дерева — такой массив Array, что Array[0] — элемент в корне, а потомки элемента Array[i] являются Array[2i+1] и Array[2i+2].

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

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

    Array [ i ] ≥ Array [ 2 i + 1 ] {displaystyle { ext{Array}}[i]geq { ext{Array}}[2i+1]}

    Array [ i ] ≥ Array [ 2 i + 2 ] {displaystyle { ext{Array}}[i]geq { ext{Array}}[2i+2]}

    при 0 ≤ i < n / 2 {displaystyle 0leq i<n/2} .

    Этот шаг требует O ( n ) {displaystyle O(n)} операций.

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

    Этот шаг требует O ( n log ⁡ n ) {displaystyle O(nlog n)} операций.

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

    Достоинства

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

    Недостатки

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

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

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

    Применение

    Алгоритм «сортировка кучей» активно применяется в ядре Linux.