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

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

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

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

[log₂N]+[log₂(N-1)]+…+[log₂2] = O(N*log₂N).

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

Быстрая сортировка выбором.Улучшить сортировку выбором можно, если после каждого прохода получать больше информации, чем просто идентификация минимального элемента.

Пример:

k1	k2	k3	k4	k5	k6	k7	k8
10
10

10 – элемент MaxInt.

k1*(N-1) – количество просмотров; log ₂ N – высота бинарного дерева.

Мы проходим от корня к листу по тому пути, по которому шел минимальный элемент (шаг 2). Затем осуществляем модификацию бинарного дерева. Общее количество модификаций: k2*log ₂ N * (N-1).

Алгоритм быстрой сортировки выбором:

1. Сравниваем пары соседних ключей и запоминаем значение меньшего ключа из каждой пары.
2. Выполняем п.1 по отношению к значениям, полученным на предыдущем шаге. Так повторяем, пока не определим наименьший ключ и не построим бинарное дерево.
3. Вносим значение корня, найденное в п.2, в массив упорядоченных ключей.
4. Проходим от корня к листу дерева, следуя по пути, отмеченному минимальным ключом, и заменяем значение в листе на наибольшее целое число.
5. Проходим от листа к корню, по пути обновляя значения в узлах дерева, и определяем новый минимальный элемент.
6. Повторяем пп.3-6, пока минимальным элементом не будет MaxInt.