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

Алгоритмы сортировки и поиска / Пирамидальная сортировка

 

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

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

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

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

Подробнее
Пирамидальная сортировка
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
#include <stdio.h>
#include <stdlib.h>
// Функция "просеивания" через кучу - формирование кучи
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[10];
  // Заполнение массива случайными числами
  for (int i = 0; i<10; i++)
    a[i] = rand() % 20 - 10;
  // Вывод элементов массива до сортировки
  for (int i = 0; i<10; i++)
    printf("%d ", a[i]);
  printf("\n");
  heapSort(a, 10); // вызов функции сортировки
  // Вывод элементов массива после сортировки
  for (int i = 0; i<10; i++)
    printf("%d ", a[i]);
  printf("\n");
  getchar();
  return 0;
}

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

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

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

(n/2)·log2n,

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


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

Комментариев к записи: 30

  • я все не понимаю, как корень дерева может иметь index = 0, как задает условие for в 42 строчке, у нас просто корень дерева при root = 0 будет сравниваться только с первым ребенком, а со вторым?


  • Здравствуйте, можете сказать какова оценка числа операций сборки пирамиды?

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


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

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


  • Добрый день. Очень нужна помощь по написанию библиотечной сортировки в Java. Информации на просторах, можно сказать, нет. Можете поделиться опытом?

  • Не могли бы вы на почту отписать код, в котором по шагам будут отображаться изменения (по итерациям)?

  • Можете подсказать, как нужно изменить код, чтобы вывести кол-во сравнений и смен в массиве? Просто свапы есть и в первой и во второй функции, как их сложить вместе?

    • Елена Вставская
      Ну, самое простое - через глобальную переменную посчитать.


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

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

  • Не работает. В строке 35 должно быть
    1
    siftDown(numbers, i, array_size - 1);
    Иначе получаем выход за границу диапазона.


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

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

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

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

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

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

  • Василий
    Что в коде нужно изменить, чтобы сортировка происходила по убыванию?

Добавить комментарий

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