Сортировка кучей :: Heap sort

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

Является «умной» модификацией-синтезом сортировки выбором и пузырьковой сортировки.

Сортировка кучей || Пирамидальная сортировка || Heap sort

Алгоритм

Основная идея — ищем максимальный элемент в неотсортированной части массива и ставим его в конец этого подмассива. В поисках максимума подмассив перестраивается в так называемое сортирующее дерево (она же двоичная куча, она же пирамида), в результате чего максимум сам «всплывает» в начало массива. После этого перемещаем максимум в конец подмассива. Затем над оставшейся частью массива снова осуществляется процедура перестройки в сортирующее дерево с последующим перемещением максимума в конец подмассива.

Сортирующее (неубывающее) дерево — дерево у которого любой родитель не меньше чем каждый из его потомков. Если сортирующее дерево невозрастающее, то, соответственно, любой родитель не больше чем каждый из его потомков.

Сложность по времени

У алгоритма нет благоприятных и вырожденных случаев. При любом входящем массиве (даже если он почти отсортирован) сортировка имеет одну и ту же временную сложность — O(n log n).

Дополнительно

Сортировка кучей используется в целом ряде других алгоритмов сортировок.

Это как её непосредственные вариации:

  • Тернарная пирамидальная сортировка
  • Сортировка декартовым деревом
  • Плавная сортировка

Так и гибридные алгоритмы:

Характеристики алгоритма

Название Сортировка кучей (Heap sort, Пирамидальная сортировка, Pyramid sort)
Автор J. W. J. Williams
Год 1964
Класс Сортировки выбором
Устойчивость Нет
Сравнения Да
Сложность по времени Лучшая O (n log n)
Средняя
Худшая
Сложность по памяти Общая O(n)
Дополнительная O(1)

Ссылки

Хабрахабр: J-сортировка

Пирамидальная сортировка в Википедии
Heap sort on Wikipedia
Реализация на различных ЯП

Добавить комментарий