Метод пирамидальной сортировки, изобретенный Д. Уильямсом, является улучшением традиционных сортировок с помощью дерева.
Пирамидой (кучей) называется двоичное дерево такое, что
{\displaystyle{a \le a[2 \cdot i + 1]}}
{\displaystyle{a \le a[2 \cdot i + 2]}}
Общая идея пирамидальной сортировки заключается в том, что сначала строится пирамида из элементов исходного массива, а затем осуществляется сортировка элементов.
Выполнение алгоритма разбивается на два этапа.
1 этап Построение пирамиды. Определяем правую часть дерева, начиная с n/2-1 (нижний уровень дерева). Берем элемент левее этой части массива и просеиваем его сквозь пирамиду по пути, где находятся меньшие его элементы, которые одновременно поднимаются вверх; из двух возможных путей выбираете путь через меньший элемент.
Например, массив для сортировки
24, 31, 15, 20, 52, 6
Расположим элементы в виде исходной пирамиды.
Номер элемента правой части (6/2-1)=2 — это элемент 15.
Результат просеивания элемента 15 через пирамиду.
Следующий просеиваемый элемент – 1, равный 31.
Затем – элемент 0, равный 24.
Разумеется, полученный массив еще не упорядочен.
Однако процедура просеивания является основой для пирамидальной сортировки. В итоге просеивания наименьший элемент оказывается на вершине пирамиды.
2 этап Сортировка на построенной пирамиде. Берем последний элемент массива в качестве текущего. Меняем верхний (наименьший) элемент массива и текущий местами. Текущий элемент (он теперь верхний) просеиваем сквозь n-1 элементную пирамиду.
Затем берем предпоследний элемент и т.д.
Продолжим процесс. В итоге массив будет отсортирован по убыванию.
Реализация пирамидальной сортировки на Си
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdlib.h>
#define SIZE 15
// Функция "просеивания" через кучу - формирование кучи
void siftDown(int* numbers, int root, int bottom)
{
int maxChild; // индекс максимального потомка
int done = 0; // флаг того, что куча сформирована
// Пока не дошли до последнего ряда
while ((root * 2 <= bottom) && (!done))
{
if (root * 2 == bottom) // если мы в последнем ряду,
maxChild = root * 2; // запоминаем левый потомок
// иначе запоминаем больший потомок из двух
else if (numbers[root * 2] > numbers[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;
// если элемент вершины меньше максимального потомка
if (numbers[root] < numbers[maxChild])
{
int temp = numbers[root]; // меняем их местами
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;
}
else // иначе
done = 1; // пирамида сформирована
}
}
// Функция сортировки на куче
void heapSort(int* numbers, int array_size)
{
// Формируем нижний ряд пирамиды
for (int i = (array_size / 2); i >= 0; i--)
siftDown(numbers, i, array_size - 1);
// Просеиваем через пирамиду остальные элементы
for (int i = array_size - 1; i >= 1; i--)
{
int temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, 0, i - 1);
}
}
int main()
{
int a[SIZE];
// Заполнение массива случайными числами
for (int i = 0; i < SIZE; i++)
a[i] = rand() % 201 - 100;
// Вывод элементов массива до сортировки
for (int i = 0; i < SIZE; i++)
printf("%4d ", a[i]);
printf("\n");
heapSort(a, SIZE); // вызов функции сортировки
// Вывод элементов массива после сортировки
for (int i = 0; i < SIZE; i++)
printf("%4d ", a[i]);
printf("\n");
getchar();
return 0;
}
Результат выполнения
Анализ алгоритма пирамидальной сортировки
Несмотря на некоторую внешнюю сложность, пирамидальная сортировка является одной из самых эффективных. Алгоритм сортировки эффективен для больших {\displaystyle{n}} .
В худшем случае требуется {\displaystyle{n \cdot log_2 \ n}} шагов, сдвигающих элементы.
Среднее число перемещений примерно равно
{\displaystyle{\frac {n}{2} \cdot log_2 \ n}},
и отклонения от этого значения относительно невелики.
Подскажите пожалуйста, что обозначает переменная root в программе, спасибо!
Это корень пирамиды
Огромное спасибо за алгоритм!!! Все отлично работает!
если в языке индексация начинаетса с 1 то индексы детей root * 2 и root * 2 + 1, а если с нуля тогда root * 2 + 1 и root * 2 + 2.
Не правильно строит сортирующее дерево и просеивает элементы.Индексы потомков root * 2 и root * 2 + 1, а должны быть root * 2 + 1 и root * 2 + 2. Инфа 100%
То как вы написали попробовал сделать, перестает работать, не сортирует. Более того, в массиве после сортировки оказывается мусор из ОП а-ля 276938395. То как приведено на сайте — все отлично работает.
Боже, огромное Вам спасибо, святая женщина
Спасибо за статью
Исходя из вашего кода, выходит, что структура пирамиды получается такой:
a[0]
|
a[1]
/ \
a[2] a[3]
/ \ / \
a[4] a[5] a[6] a[7]
/ \
a[8] a[9]
Не понимаю, на основании чего Вы сделали такой вывод. Структура пирамиды изображена на рисунке.
В вашей программе если в 11 строчке условие верно, то maxChild станет равным array_size. И тогда в 19 строке идёт вызов элемента массива numbers[array_size], но там лежит мусор (выход за пределы массива). Здесь не Паскаль и нумерация элементов идёт с нуля.
Условие в строке 11 используется для случаев рекурсивного вызова функции просеивания.
Вызов в строке 35 (при формировании кучи) не сможет выйти за границы массива, поскольку i <= (array_size / 2) - 1, а следующее изменение root уже выйдет за границы массива.
Вызов в строке 42 осуществляется для количества элементов меньше, чем задано в массиве (параметр bottom функции shiftDown())
Замечательно объяснено и проиллюстрировано. Не то,что нам на лекции рассказывали
А если в массиве будет нечётное количество элементов? Когда сработает (root * 2 == bottom)?
Здесь мы проверяем, какое начальное значение maxChild взять. Если у узла нет потомков, берется само значение узла. Если есть, берём большее значение из двух.
С нечётным количеством элементов можете сами проверить этот алгоритм.