Определение времени работы алгоритма пирамидальной сортировки в худшем случае

Время на прочтение
8 мин

Количество просмотров 11K

Сортировку кучей (она же — пирамидальная сортировка) на Хабре уже поминали добрым словом не раз и не два, но это всегда была достаточно общеизвестная информация. Обычную бинарную кучу знают все, но ведь в теории алгоритмов также есть:

n-нарная куча; куча куч, основанная на числах Леонардо; дерамида (гибрид кучи и двоичного дерева поиска); турнирная мини-куча; зеркальная (обратная) куча; слабая куча; юнгова куча; биномиальная куча; и бог весть ещё какие кучи…

И умнейшие представители computer science в разные годы предложили свои алгоритмы сортировки с помощью этих пирамидальных структур. Кому интересно, что у них получилось — для тех начинаем небольшую серию статей, посвящённую вопросам сортировки с помощью этих структур. Мир куч многообразен — надеюсь, вам будет интересно.

Статья написана при поддержке компании EDISON.

Мы занимаемся разработкой мобильных приложений и предоставляем услуги по тестированию программного обеспечения.

Мы очень любим теорию алгоритмов!

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

Сортировка обычным выбором — это брутфорс. Если в поисках максимумов просто линейно проходить по массиву, то временнáя сложность такого алгоритма не может превысить O(n²).

Куча

Наиболее эффективный способ работать с максимумами в массиве — это организовать данные в специальную древовидную структуру, известную как куча. Это дерево, в котором все родительские узлы не меньше чем узлы-потомки.

Другие названия кучи — пирамида, сортирующее дерево.

Давайте разберём, как это можно легко и почти бесплатно представить массив в виде дерева.

Возьмём самый первый элемент массива и будем считатть, что это корень дерева — узел 1-го уровня. Следующие 2 элемента — это узлы 2-го уровня, правый и левый потомки корневого элемента. Следующие 4 элемента — это узлы 3-го уровня, правые/левые потомки второго/третьего элемента массива. Следующие 8 элементов — узлы 4-го уровня, потомки элементов 3-го уровня. И т.д. На этом изображении узлы бинарного дерева наглядно расположены строго под соответствующими элементами в массиве:

Хотя, деревья на диаграммах чаще изображают в такой развёртке:

Если смотреть под таким углом, то тогда понятно почему сортировку кучей называют пирамидальной сортировкой. Хотя, это примерно тоже самое, как если шахматного слона называть офицером, ладью — турой, а ферзя — королевой.

Индексы потомков для i-го элемента определяются элементарно (если индекс самого первого элемента массива считать равным 0, как принято в подавляющем большинстве языков программирования):

Левый потомок: 2 × i + 1
Правый потомок: 2 × i + 2

(У меня на диаграммах и анимациях традиционно индексы массивов начинаются с 1, там формулы слегка отличаются: левый потомок:

2 × i

и правый потомок:

2 × i + 1

, но это уже мелкие арифметические нюансы).

Если получающиеся по этим формулам индексы потомков выходят за пределы массива, значит у i-го элемента потомков нет. Также может статься что у i-го элемента есть левый потомок (приходится на самый последний элемент массива, в котором нечётное количество элементов), но уже нет правого.

Итак, любой массив можно легко представить в виде дерева, однако это пока ещё не куча, потому что, в массиве некоторые элементы-потомки могут оказаться больше чем их элементы-родители.

Чтобы наше дерево, созданное на основе массива, стало кучей, его нужно как следует просеять.

Просейка

Душой сортировки кучей является просейка.

Просеивание для элемента состоит в том, что если он меньше по размеру чем потомки, объединённых в неразрывную цепочку, то этот элемент нужно переместить как можно ниже, а бо́льших потомков по ветке поднять наверх на 1 уровень.

На изображении показан путь просейки для элемента. Синим цветом обозначен элемент для которого осуществляется просейка. Зелёный цвет — бо́льшие потомки вниз по ветке. Они будут подняты на один уровень вверх, поскольку по величине превосходят синий узел, для которого делается просейка. Сам элемент из самого верхнего синего узла будет перемещён на место самого нижнего потомка из зелёной цепочки.

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

На этом изображении элементы массива перераспределены так, что он уже разложен именно в кучу. Хотя массив раскладывается в сортирующее дерево, сам он пока что не отсортирован (ни по возрастанию ни по убыванию), хотя все потомки в дереве меньше чем их родительские узлы. Но зато самый максимальный элемент в сортирующем дереве всегда находится в главном корне, что очень важно.

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

Алгоритм на самом деле простой:

• Этап 1. Формируем из всего массива сортирующее дерево. Для этого проходим справа-налево элементы (от последних к первым) и если у элемента есть потомки, то для него делаем просейку.
• Этап 2. Максимумы ставим в конец неотсортированной части массива. Так как данные в массиве после первого этапа представляют из себя сортирующее дерево, максимальный элемент находится на первом месте в массиве. Первый элемент (он же максимум) меняем с последним элементом неотсортированной части массива местами. После этого обмена максимум оказался своём окончательном месте, т.е. максимальный элемент отсортирован. Неотсортированная часть массива перестала быть сортирующим деревом, но это исправляется однократной просейкой — в результате чего на первом месте массива оказывается предыдущий по величине максимальный элемент. Действия этого этапа снова повторяются для оставшейся неупорядоченной области, до тех пор пока максимумы поочерёдно не будут перемещены на свои окончательные позиции.

Код на Питоне классической реализации пирамидальной сортировки:

# Основной алгоритм сортировки кучей
def HeapSort(data):

    # Формируем первоначальное сортирующее дерево
    # Для этого справа-налево перебираем элементы массива
    # (у которых есть потомки) и делаем для каждого из них просейку
    for start in range((len(data) - 2) / 2, -1, -1):
        HeapSift(data, start, len(data) - 1) 

    # Первый элемент массива всегда соответствует корню сортирующего дерева
    # и поэтому является максимумом для неотсортированной части массива.
    for end in range(len(data) - 1, 0, -1): 
        # Меняем этот максимум местами с последним 
        # элементом неотсортированной части массива
        data[end], data[0] = data[0], data[end]
        # После обмена в корне сортирующего дерева немаксимальный элемент
        # Восстанавливаем сортирующее дерево
        # Просейка для неотсортированной части массива
        HeapSift(data, 0, end - 1)
    return data

# Просейка свеху вниз, в результате которой восстанавливается сортирующее дерево
def HeapSift(data, start, end):

    # Начало подмассива - узел, с которого начинаем просейку вниз
    root = start 
    
    # Цикл просейки продолжается до тех пор,
    # Пока встречаются потомки, большие чем их родитель
    while True:

        child = root * 2 + 1 # Левый потомок
        # Левый потомок за пределами подмассива - завершаем просейку
        if child > end: break 

        # Если правый потомок тоже в пределах подмассива,
        # то среди обоих потомков выбираем наибольший
        if child + 1 <= end and data[child] < data[child + 1]:
            child += 1

        # Если больший потомок больше корня, то меняем местами
        # при этом больший потомок сам становится корнем, 
        # от которого дальше опускаемся вниз по дереву
        if data[root] < data[child]:
            data[root], data[child] = data[child], data[root]
            root = child
        else:
            break

Сложность алгоритма

Чем хороша простая куча — её не нужно отдельно хранить, в отличие от других видов деревьев (например, двоичное дерево поиска на основе массива прежде чем использовать нужно сначала создать). Любой массив уже является деревом, в котором прямо на ходу можно сразу определять родителей и потомков. Сложность по дополнительной памяти O(1), всё происходит сразу на месте.

Что касается сложности по времени, то она зависит от просейки. Однократная просейка обходится в

O(log n)

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

O(n log n)

. На втором этапе мы при вынесении n текущих максимумов из кучи делаем однократную просейку для оставшейся неотсортированной части, т.е. этот этап также стоит нам

O(n log n)

.

Итоговая сложность по времени: O(n log n) + O(n log n) = O(n log n).
При этом у пирамидальной сортировки нет ни вырожденных ни лучших случаев. Любой массив будет обработан на приличной скорости, но при этом не будет ни деградации ни рекордов.

Сортировка кучей в среднем работает несколько медленнее чем быстрая сортировка. Но для quicksort можно подобрать массив-убийцу, на котором компьютер зависнет, а вот для heapsort — нет.

Сортировка тернарной кучей :: Ternary heapsort

Давайте рассмотрим троичную кучу. От двоичной она, вы не поверите, отличается только тем, что у родительских узлов максимум не два, а три потомка. В тернарной куче для i-го элемента индексы его трёх потомков вычисляются аналогично (если у первого элемента индекс = 0):

Левый потомок: 3 × i + 1
Средний потомок: 3 × i + 2
Правый потомок: 3 × i + 3

(Если индексы начинать с 1, как на анимациях в этой статье, то в этих формулах надо просто отнять единицу).

Процесс сортировки:

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

Сортировка n-нарной кучей :: N-narny heapsort

Разумеется, можно не останавливаться на достигнутом и адаптировать сортировку кучей для любого числа потомков. Может быть, если и дальше увеличивать количества потомков, можно существенно повысить скорость процесса?

Для i-го элемента массива индексы (если отсчитывать их с нуля) его N потомков вычисляются очень просто:

1-й потомок: N × i + 1
2-й потомок: N × i + 2
3-й потомок: N × i + 3
…
N-й потомок: N × i + N

Код на Python сортировки N-нарной кучей:

# Основной алгоритм сортировки кучей для N потомков
def NHeapSort(data):

    n = 3 # Сколько потомков у родителя

    # Формируем первоначальное сортирующее дерево
    # Для этого справа-налево перебираем элементы массива
    # (у которых есть потомки) и делаем для каждого из них просейку
    for start in range(len(data), -1, -1):
        NHeapSift(data, n, start, len(data) - 1) 

    # Первый элемент массива всегда соответствует корню сортирующего дерева
    # и поэтому является максимумом для неотсортированной части массива.
    for end in range(len(data) - 1, 0, -1): 
        # Меняем этот максимум местами с последним 
        # элементом неотсортированной части массива
        data[end], data[0] = data[0], data[end]
        # После обмена в корне сортирующего дерева немаксимальный элемент
        # Восстанавливаем сортирующее дерево
        # Просейка для неотсортированной части массива
        NHeapSift(data, n, 0, end - 1)
    return data
    
# Просейка сверху-вниз для родителя у которого N потомков
def NHeapSift(data, n, start, end):
    
    # Начало подмассива - узел, с которого начинаем просейку вниз
    root = start 

    while True:
        
        # Первого потомка (если он в пределах подмассива)
        # назначаем максимальным потомком
        child = root * n + 1
        if child > end: 
            break 

        max = child
        
        # Среди потомков определяем максимального
        for k in range(2, n + 1):
            current = root * n + k
            if current > end:
                break
                
            if data[current] > data[max]:
                max = current
        
        # Если максимальный потомок больше родителя
        # то меняем их местами и этот потомок сам
        # становится родителем
        if data[root] < data[max]:
            data[root], data[max] = data[max], data[root]
            root = max
        else:
            break

Впрочем, больше — не значит, лучше. Если довести ситуацию до предела и брать N потомков для массива из N элементов, то сортировка кучей деградирует до сортировки обычным выбором. Причём это будет ещё и ухудшенная версия сортировки выбором, так как будут совершаться бессмысленные телодвижения: просейка сначала будет ставить максимум на первое место в массиве, а потом будет отправлять максимум в конец (в selection sort отправка максимума в конец происходит сразу).

Если троичная куча минимально обгоняет двоичную, то четверичная уже проигрывает. Поиск максимального потомка среди нескольких становится слишком дорогим.

Трейлер следующей серии

Итак, основной недостаток бинарной/тернарной/n-нарной кучи — невозможность прыгнуть в своей сложности выше чем

O(n log n)

. Выход из тупика — использовать в сортировке более усложнённые разновидности кучи. Через неделю ознакомимся с тем, что по этому поводу думает Эдсгер Дейкстра.

Кликните по анимации для перехода в статью со следующей сортировкой кучей

Ссылки

Heap / Пирамида

Статьи серии:

• Excel-приложение AlgoLab.xlsm
• Сортировки обменами
• Сортировки вставками
• Сортировки выбором
  • Сортировки кучей: n-нарные пирамиды
  • Сортировки кучей: числа Леонардо
  • Сортировки кучей: слабая куча
  • Сортировки кучей: декартово дерево
  • Сортировки кучей: турнирное дерево
  • Сортировки кучей: восходящая просейка
• Сортировки слиянием
• Сортировки распределением
• Гибридные сортировки

В приложение AlgoLab добавлена сортировка n-нарной кучей. Чтобы выбрать количество потомков, в комментарии к ячейке этой сортировки нужно указать число для n. Диапазон возможных значений — от 2 до 5 (больше нет смысла, потому что при n >= 6 анимация уже при трёх уровнях вложенности при нормальном масштабе гарантировано не помещается на экране).

В некоторых
приложениях (например, в задачах
управления оборудованием в реальном
времени) крайне важно иметь гарантию,
что время работы критических ветвей
программы даже в самом плохом случае
не превысит некоторой заданной величины.
Для таких задач использование QuickSortможет оказаться неприемлемым ввиду
названного выше недостатка этого
алгоритма – времени работы порядкаO(n²)в худшем случае. В этой ситуации следует
использовать такой алгоритм, который
работает гарантированно быстро даже в
худшем случае.

Наиболее известным
из таких алгоритмов является HeapSort,
который по-русски принято называть
пирамидальной сортировкой.

В основе алгоритма
лежит понятие пирамиды.

Массив Aназывается пирамидой, если для всех его
элементов выполнены следующие неравенства:

(3.1)

Смысл неравенств
(3.1) можно
наглядно пояснить на рис.3.1.

Рис. 3.1.
Представление пирамиды в виде дерева

На рисунке
массив-пирамида из 10 элементов изображен
в виде сбалансированного бинарного
дерева, вершины которого пронумерованы
сверху вниз и слева направо. При этом
элемент a_kвсегда будет в дереве «отцом» элементовa_2kиa_2k+1(если такие элементы имеются). Тогда
неравенства (3.1)
означают, что значение «отца» должно
быть не меньше, чем значения каждого из
«сыновей».

Следует, однако,
помнить, что пирамида – это не дерево,
а массив с определенными свойствами, а
изображение пирамиды в виде дерева дано
только для наглядности.

Пирамида вовсе не
обязательно является сортированным
массивом, однако она служит удобным
промежуточным результатом при сортировке.
Отметим, что первый элемент пирамиды
(a₁)
всегда является максимальным элементом
массива.

Работа алгоритма
HeapSortсостоит из двух
последовательных фаз. На первой фазе
исходный массив перестраивается в
пирамиду, а на второй фазе из пирамиды
строится сортированный массив.

Основной операцией,
используемой как на первой, так и на
второй фазах сортировки, является так
называемое просеиваниеэлемента
сквозь пирамиду.

Предположим, что
неравенства (3.1)
выполнены для элементов пирамиды,
начиная с индексаk+1(т.е. для
элементовa_k+1,a_k+2,
… ,a_n).
Процедура просеивания элементаa_kдолжна обеспечить выполнение (3.1)
дляa_kи при этом не нарушить этих неравенств
дляa_k+1,a_k+2,
… ,a_n.

Алгоритм просеивания
заключается в следующем.

1. Если a_kне имеет сыновей (т.е.2k > n), то
   просеивание закончено.

2. Если a_kимеет ровно одного сына (т.е.2k = n),
   то присвоитьl := nи перейти к
   шагу 4.

3. Сравнить значения
   двух сыновей вершины a_k:
   еслиa_2k>a_2k+1,
   тоl := 2k,
   иначеl := 2k + 1(т.е.l– это индекс большего из
   сыновейa_k).

4. Сравнить значения
   элемента a_kсо значением его большего сынаa_l:
   еслиa_k<a_l,
   то поменять местамиa_kиa_l.

5. Присвоить k :=
   lи перейти к шагу 1.

На рис. 3.1выполнение просеивания выглядит
следующим образом: вершина дерева,
значение которой меньше значения хотя
бы одного из ее сыновей, опускается
вдоль одной из ветвей дерева, пока не
займет свое законное место. При этом
все остальные вершины дерева за пределами
этой ветви остаются неизменными¹.

Нетрудно видеть,
что максимально возможное число
повторений цикла в процедуре просеивания
не превышает log₂n(поскольку на каждой итерации значениеkувеличивается по крайней мере
в 2 раза).

Теперь нетрудно
описать алгоритм сортировки HeapSortв целом, используя понятие просеивания
элемента.

Первая фаза
алгоритма (построение пирамиды)начинается с вычисления наибольшего
индекса элементаa_k,
у которого есть хотя бы один сын. Очевидно,k := n div 2.
Затем выполняется просеивание элементовa_k,a_k–1,a_k–2,
…,a₂,a₁.
На этом построение пирамиды завершено.

Вторая фаза
алгоритма (построение сортированного
массива)состоит из следующих шагов.

1. Поменять местами
   элементы a₁иa_n.
   Напомним, что в пирамидеa₁– максимальный элемент; после обмена
   он будет стоять на последнем месте.

2. Присвоить
   n := n — 1. Тем самым мы
   как бы исключаем последний элемент из
   пирамиды и включаем его в сортированный
   массив, который должен быть результатом
   работы алгоритма.

3. Поскольку после
   обмена для нового элемента a₁могло нарушиться свойство (3.1),
   выполнить просеиваниеa₁.
   После этого на местеa₁окажется максимальный из оставшихся
   элементов пирамиды.

4. Если n > 1,
   то перейти к шагу 1, иначе сортировка
   завершена.

На каждой итерации
второй фазы происходит исключение из
пирамиды максимального из оставшихся
в ней элементов. Этот элемент записывается
на подобающее ему место в сортированном
массиве. К концу работы алгоритма вся
пирамида превращается в сортированный
массив.

Оценим время работы
каждой фазы алгоритма HeapSort.
Первая фаза состоит изn/2операций
просеивания, каждая из которых включает
не болееlog₂(n)итераций цикла. Отсюда можем легко
получить для первой фазы оценкуT_макс(n) = O(nlog(n)).
Однако эта оценка чересчур грубая. В
дальнейшем нам понадобится более точная
оценка времени работы первой фазыHeapSort. Чтобы получить такую
оценку, рассмотрим рис.3.2.

Рис. 3.2.
Число итераций просеивания при построении
пирамиды

Из числа всех nэлементов массиваAпримерно половина (n/2) не имеет
сыновей и не требует просеивания (т.е.
число итераций просеивания равно 0).
Четверть элементов (n/4) имеет
сыновей, но не имеет внуков, для этих
элементов может быть выполнено не больше
одной итерации просеивания. Для одной
восьмой части элементов (n/8)
могут быть выполнены две итерации, для
одной шестнадцатой (n/16) – три
итерации и т.д. Суммарное число итераций
просеивания определится формулой:n (01/2
+ 11/4
+ 21/8
+ 31/16
+ …). Тряхнув воспоминаниями о матанализе,
можно вычислить значение суммы ряда в
скобках; это значение равно 1. Таким
образом, получаем линейную оценку
времени для первой фазы:T_макс(n) = O(n).

Вторая фаза
алгоритма в основном представляет собой
просеивание элементов сквозь уменьшающуюся
пирамиду. Число итераций цикла можно
примерно оценить как сумму log₂(n)
+ log₂(n–1)
+ log₂(n–2)
+ … + log₂(3) + log₂(3).
Поверим без доказательства, что с
точностью доO-большого эта сумма
даетT_макс(n) = O(nlog(n)).

Время работы
алгоритма в целом определяется более
трудоемкой второй фазой и удовлетворяет
оценке T_макс(n) = O(nlog(n)).
Можно доказать, что такая же оценка
справедлива и для среднего времени
сортировки:T_ср(n) = O(nlog(n)).
Таким образом,HeapSortпредставляет собой алгоритм сортировки,
который гарантирует достаточно быструю
работу даже в случае самых неудачных
исходных данных. ЭтимHeapSortвыгодно отличается отQuickSort,
который такой гарантии не дает. С другой
стороны, практика показывает, что в
среднем алгоритмHeapSortработает примерно вдвое медленнее, чемQuickSort.

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

Алгоритм

Необходимо отсортировать массив , размером . Построим на базе этого массива за кучу для максимума. Так как максимальный элемент находится в корне, то если поменять его местами с , он встанет на своё место. Далее вызовем процедуру , предварительно уменьшив на . Она за просеет на нужное место и сформирует новую кучу (так как мы уменьшили её размер, то куча располагается с по , а элемент находится на своём месте). Повторим эту процедуру для новой кучи, только корень будет менять местами не с , а с . Делая аналогичные действия, пока не станет равен , мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.

Реализация

• — массив, который необходимо отсортировать
• — количество элементов в нём
• — процедура, которая строит из передаваемого массива кучу для максимума в этом же массиве
• — процедура, которая просеивает вниз элемент в куче из элементов, находящихся в начале массива

 fun heapSort(A : list <T>):
   buildHeap(A)
   heapSize = A.size
   for i = 0 to n - 1
     swap(A[0], A[n - 1 - i])
     heapSize--
     siftDown(A, 0, heapSize)

Сложность

Операция работает за . Всего цикл выполняется раз. Таким образом сложность сортировки кучей является .

Достоинства:

• худшее время работы — ,
• требует дополнительной памяти.

Недостатки:

• неустойчивая,
• на почти отсортированных данных работает столь же долго, как и на хаотических данных.

Пример

Пусть дана последовательность из элементов .

JSort

JSort является модификацией сортировки кучей, которую придумал Джейсон Моррисон (Jason Morrison).
Алгоритм частично упорядочивает массив, строя на нём два раза кучу: один раз передвигая меньшие элементы влево, второй раз передвигая большие элементы вправо. Затем к массиву применяется
сортировка вставками, которая при почти отсортированных данных работает за .

Достоинства:

• В отличие от сортировки кучей, на почти отсортированных массивах работает быстрее, чем на случайных.
• В силу использования сортировки вставками, которая просматривает элементы последовательно, использование кэша гораздо эффективнее.

Недостатки:

• На длинных массивах, возникают плохо отсортированные последовательности в середине массива, что приводит к ухудшению работы сортировки вставками.

Алгоритм

Построим кучу для минимума на этом массиве.
Тогда наименьший элемент окажется на первой позиции, а левая часть массива окажется почти отсортированной, так как ей будут соответствовать верхние узлы кучи.
Теперь построим на этом же массиве кучу так, чтобы немного упорядочить правую часть массива. Эта куча должна быть кучей для максимума и быть «зеркальной» к массиву, то есть чтобы её корень соответствовал последнему элементу массива.
К получившемуся массиву применим сортировку вставками.

Сложность

Построение кучи занимает . Почти упорядоченный массив сортировка вставками может отсортировать , но в худшем случае за .

Таким образом, наихудшая оценка Jsort — .

Пример

Рассмотрим, массив =

Построим на этом массиве кучу для минимума:

Массив выглядит следующим образом:

Заметим, что начало почти упорядочено, что хорошо скажется на использовании сортировки вставками.

Построим теперь зеркальную кучу для максимума на этом же массиве.

Массив будет выглядеть следующим образом:

Теперь и конец массива выглядит упорядоченным, применим сортировку вставками и получим отсортированный массив.

См. также

• Сортировка слиянием
• Быстрая сортировка
• Теорема о нижней оценке для сортировки сравнениями

Источники информации

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. Издательский дом «Вильямс», 2005. ISBN 5-8459-0857-4
• Wikipedia — Heapsort
• Wikipedia — JSort
• Хабрахабр — Описание сортировки кучей и JSort
• Википедия — Пирамидальная сортировка

a[i] ≤ a[2i+1];

a[i] ≤ a[2i+2].

24,   31,  15,   20,   52,   6

Результат выполнения

Анализ алгоритма пирамидальной сортировки

Несмотря на некоторую внешнюю сложность, пирамидальная сортировка является одной из самых эффективных. Алгоритм сортировки эффективен для больших n. В худшем случае требуется n·log₂n шагов, сдвигающих элементы. Среднее число перемещений примерно равно

(n/2)·log₂n,

и отклонения от этого значения относительно невелики.

Назад: Алгоритмы сортировки и поиска

Получив целочисленный массив, отсортируйте его, используя алгоритм пирамидальной сортировки в C, C++, Java и Python.

Обзор Heapsort

Heapsort — это на месте, алгоритм сортировки на основе сравнения и может рассматриваться как улучшенный сортировка выбором поскольку он делит ввод на отсортированную и несортированную области. Он итеративно сжимает несортированную область, извлекая наибольший/наименьший элемент и перемещая его в отсортированную область. Улучшение состоит в использовании структуры данных кучи, а не в поиске с линейным временем для нахождения максимума. Heapsort не обеспечивает стабильной сортировки, что означает, что реализация не сохраняет входной порядок одинаковых элементов в отсортированном выходе. Как правило, медленнее, чем другие O(n.log(n)) алгоритмы сортировки, такие как быстрая сортировка, Сортировка слиянием.

Алгоритм heapsort можно разделить на две части:

• На первом этапе из входных данных строится куча. Мы можем сделать это в O(n) время.
• На втором этапе создается отсортированный массив путем многократного удаления самого большого/наименьшего элемента из кучи (корень кучи) и вставки его в массив. Куча обновляется(heapify-down вызывается на корневом узле) после каждого удаления для сохранения свойства кучи. Как только все элементы будут удалены из кучи, мы получим отсортированный массив. Это делается в O(n.log(n)) время, так как нам нужно поп n элементы, где каждое удаление включает в себя постоянный объем работы, а одна операция heapify занимает O(log(n)) время.

Как построить кучу?

Наивным решением было бы начать с пустой кучи и многократно вставлять в нее каждый элемент входного списка. Проблема с этим подходом в том, что он работает в O(n.log(n)) время на входе, содержащем n элементы, как он выполняет n вставки в O(log(n)) стоимость каждого.

Мы можем построить кучу в O(n) время, произвольно помещая входные элементы в массив кучи. Затем, начиная с последнего внутреннего узла кучи (присутствует по индексу (n-2)/2 в массиве), вызовите процедуру heapify на каждом узле до корневого узла (до индекса 0). Поскольку процедура heapify ожидает, что левый и правый дочерние элементы узла будут кучами, начните с последнего внутреннего узла (поскольку конечные узлы уже являются кучами) и двигайтесь вверх уровень за уровнем.

Можно утверждать, что основная операция heapify с кучей выполняется в O(log(n)) время, и мы вызываем heapify примерно n/2 times (по одному на каждый внутренний узел). Таким образом, временная сложность приведенного выше решения равна O(n.log(n)). Однако оказалось, что анализ не плотно.

Когда вызывается heapify, время выполнения зависит от того, насколько далеко элемент может сместиться в дереве до того, как процесс завершится. Другими словами, это зависит от высоты элемента в куче. В худшем случае элемент может опуститься на конечный уровень. Считаем проделанную работу уровень за уровнем.

Как мы видим, не все операции heapify O(log(n)), и именно поэтому, проведя тщательный анализ, мы можем получить O(n) время.

Практикуйте этот алгоритм

1. Реализация Heapsort на месте

Heapsort можно выполнять на месте. Мы можем сделать это с помощью

Идея состоит в том, чтобы разделить массив на две части — кучу и отсортированный массив. По мере того, как каждая операция выталкивания освобождает место в конец массива в двоичной куче, перемещайте извлеченный элемент в свободное пространство. Таким образом, первый извлеченный элемент (максимальный элемент) переместится в последнюю позицию в массиве, второй извлеченный элемент (следующий максимальный элемент) переместится в предпоследнюю позицию в массиве и так далее… наконец, когда все элементы вытолкнут из кучи, мы получим массив, отсортированный по возрастанию.

Временная сложность приведенного выше алгоритма равна O(n.log(n)), куда n является входным размером и требует O(n) неявное пространство для стека вызовов.

2. Неуместная реализация Heapsort

The неуместный Алгоритм heapsort может быть реализован на C++ и Java следующим образом:

Временная сложность приведенного выше алгоритма равна O(n.log(n)), а вспомогательное пространство, используемое программой, равно O(n), куда n это размер ввода.

 
Упражнение: Сортировка элементов по убыванию с помощью heapsort

 
Использованная литература:

1. https://en.wikipedia.org/wiki/Heapsort

2. https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity