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

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

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

Пирамидой (кучей) называется двоичное дерево такое, что

{\displaystyle{a \le a[2 \cdot i + 1]}}
{\displaystyle{a \le a[2 \cdot i + 2]}}

Подробнее

Пирамида
{\displaystyle{a[0]}} — минимальный элемент пирамиды.

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

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

1 этап Построение пирамиды. Определяем правую часть дерева, начиная с n/2-1 (нижний уровень дерева). Берем элемент левее этой части массива и просеиваем его сквозь пирамиду по пути, где находятся меньшие его элементы, которые одновременно поднимаются вверх; из двух возможных путей выбираете путь через меньший элемент.

Например, массив для сортировки

24,   31,  15,   20,   52,   6

Расположим элементы в виде исходной пирамиды.

Номер элемента правой части (6/2-1)=2 — это элемент 15.

Результат просеивания элемента 15 через пирамиду.

Следующий просеиваемый элемент – 1,  равный 31.

Затем – элемент 0, равный 24.

Разумеется, полученный массив еще не упорядочен.

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

2 этап Сортировка на построенной пирамиде. Берем последний элемент массива в качестве текущего. Меняем верхний (наименьший) элемент массива и текущий местами. Текущий элемент (он теперь верхний) просеиваем сквозь n-1 элементную пирамиду.

Затем берем предпоследний элемент и т.д.

Продолжим процесс. В итоге массив будет отсортирован по убыванию.

Реализация пирамидальной сортировки на Си

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 <stdio.h>
#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}},

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

15 комментариев к “Пирамидальная сортировка”

  1. Евгений

    Подскажите пожалуйста, что обозначает переменная root в программе, спасибо!

  2. Максим

    если в языке индексация начинаетса с 1 то индексы детей root * 2 и root * 2 + 1, а если с нуля тогда root * 2 + 1 и root * 2 + 2.

  3. Не правильно строит сортирующее дерево и просеивает элементы.Индексы потомков root * 2 и root * 2 + 1, а должны быть root * 2 + 1 и root * 2 + 2. Инфа 100%

    1. Роман

      То как вы написали попробовал сделать, перестает работать, не сортирует. Более того, в массиве после сортировки оказывается мусор из ОП а-ля 276938395. То как приведено на сайте — все отлично работает.

  4. Дмитрий

    Исходя из вашего кода, выходит, что структура пирамиды получается такой:
    a[0]
    |
    a[1]
    / \
    a[2] a[3]
    / \ / \
    a[4] a[5] a[6] a[7]
    / \
    a[8] a[9]

    1. Елена Вставская

      Не понимаю, на основании чего Вы сделали такой вывод. Структура пирамиды изображена на рисунке.

  5. Наталья

    В вашей программе если в 11 строчке условие верно, то maxChild станет равным array_size. И тогда в 19 строке идёт вызов элемента массива numbers[array_size], но там лежит мусор (выход за пределы массива). Здесь не Паскаль и нумерация элементов идёт с нуля.

    1. Елена Вставская

      Условие в строке 11 используется для случаев рекурсивного вызова функции просеивания.
      Вызов в строке 35 (при формировании кучи) не сможет выйти за границы массива, поскольку i <= (array_size / 2) - 1, а следующее изменение root уже выйдет за границы массива.
      Вызов в строке 42 осуществляется для количества элементов меньше, чем задано в массиве (параметр bottom функции shiftDown())

  6. Начнем-с

    Замечательно объяснено и проиллюстрировано. Не то,что нам на лекции рассказывали

     

  7. Александр

    А если в массиве будет нечётное количество элементов? Когда сработает (root * 2 == bottom)?

    1. Елена Вставская

      Здесь мы проверяем, какое начальное значение maxChild взять. Если у узла нет потомков, берется само значение узла. Если есть, берём большее значение из двух.
      С нечётным количеством элементов можете сами проверить этот алгоритм.

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Прокрутить вверх