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

Пирамидальная сортировка является улучшенной сортировкой выбором. Из массива, состоящего из N элементов, выбирается максимальный и меняется местами с последним. Затем рассматривается массив из N=N-1 элементов. Процесс повторяется до тех пор, пока количество рассматриваемых элементов больше одного. Пирамидальная сортировка отличается от сортировки выбором поиском максимального элемента. Чтобы понять пирамидальную сортировку, массив нужно интерпретировать как бинарное дерево, в корне которого находится первый элемент массива, на втором уровне – второй и третий, на третьем – с четвѐртого по седьмой и т.д.

Поиск максимального элемента массива в этом алгоритме основан на понятии пирамиды. Дерево (поддерево) является пирамидой, если каждый элемент в нѐм больше или равен элементам, которые являются его сыновьями. Корень пирамиды – максимальный элемент массива. Пирамида для массива M (см. табл.3.4) представлена на рис.3.2.

Построив пирамиду для массива, можно в соответствии с алгоритмом сортировки вставками, максимальный элемент, который находится в корне пирамиды (корень пирамиды – первый элемент массива), поменять местами с последним элементом массива. В результате получим массив М и его представление без последнего элемента в виде дерева на рис.3.3.

Для того, чтобы дерево перестроить в пирамиду, достаточно значение из корня дерева ―опустить вниз‖ меняя его местами с сыном, имеющим наибольшее значение. Обмен производить до тех пор, пока есть сын, больший чем элемент в корне. При перестроении дерева в пирамиду корневой элемент опускается на седьмой, а третий и седьмой поднимаются соответственно на первый и третий. Пирамида построена и теперь корень можно поменять с последним элементом дерева и в дальнейшем его не обрабатывать. Для полной сортировки процесс повторяется, пока в дереве количество вершин больше одного.

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

Пусть дерево массива на нижнем (нулевом) уровне содержит максимальное число вершин. Для построения пирамиды из произвольного дерева (первая часть алгоритма) обработать все вершины, начиная с первого уровня. Для обработки вершины на i-том уровне число сравнений пропорционально i. Число вершин на i-том уровне равно 2[log2N]-1 , а всего уровней m=[log2N], следовательно общее число сравнений определяется формулой

1*2[log2N]-1 + 2*2[log2N]-2 + … +m*2[log2N]-m = O(N).

Во второй части алгоритма последовательно обрабатываются с N, N-1, … ,2 вершинами. Число сравнений для перестройки дерева, состоящего из i вершин, в пирамиду пропорционально [log2i], следовательно, общее число сравнений

[log2N]+[log2(N-1)]+…+[log22] = O(N*log2N).

Т.о. порядок функции ВС алгоритма пирамидальной сортировки O(N*log2N).

Сортировка обменом (пузырьком)