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

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

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

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

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 элементную пирамиду. Затем берем предпоследний элемент и т.д.
Сортировка на пирамиде

Сортировка на пирамиде

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

Сортировка на пирамиде

Сортировка на пирамиде

Сортировка на пирамиде

Сортировка на пирамиде

Сортировка на пирамиде

Сортировка на пирамиде

Сортировка на пирамиде

Сортировка на пирамиде

Реализация пирамидальной сортировки
#include <stdio.h>
#include <stdlib.h>
void siftDown(int *numbers, int root, int bottom) {
  int done, maxChild, temp;
  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]) {
      temp = numbers[root];
      numbers[root] = numbers[maxChild];
      numbers[maxChild] = temp;
      root = maxChild;
    }  else
      done = 1;
  }
}
void heapSort(int *numbers, int array_size) {
  int i, temp;
  for (i = (array_size / 2)-1; i >= 0; i--)
    siftDown(numbers, i, array_size);
  for (i = array_size-1; i >= 1; i--) {
    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, и отклонения от этого значения относительно невелики.
Назад


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

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

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