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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Анимированная схема алгоритма

Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»[1]) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов.[2] Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).

Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.

История создания[править | править вики-текст]

Пи­ра­ми­даль­ная сор­ти­ров­ка бы­ла пред­ло­же­на Дж. Уи­льям­сом в 1964 го­ду.[1]

Алгоритм[править | править вики-текст]

Пример сортирующего дерева
структура хранения данных сортирующего дерева

Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены условия:

  1. Каждый лист имеет глубину либо d, либо d-1, d — максимальная глубина дерева.
  2. Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.

Удобная структура данных для сортирующего дерева — такой массив Array, что Array[1] — элемент в корне, а потомки элемента Array[i] являются Array[2i] и Array[2i+1].

Алгоритм сортировки будет состоять из двух основных шагов:

1. Выстраиваем элементы массива в виде сортирующего дерева:

\text{Array}[i]\geq \text{Array}[2i]

\text{Array}[i]\geq \text{Array}[2i+1]

при 1\leq i<n/2.

Этот шаг требует O(n) операций.

2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем Array[1] и Array[n], преобразовываем Array[1], Array[2], … , Array[n-1] в сортирующее дерево. Затем переставляем Array[1] и Array[n-1], преобразовываем Array[1], Array[2], … , Array[n-2] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[1], Array[2], … , Array[n] — упорядоченная последовательность.

Этот шаг требует O(n \log n) операций.

Достоинства и недостатки[править | править вики-текст]

Достоинства

  • Имеет доказанную оценку худшего случая O(n\cdot\log n).
  • Сортирует на месте, то есть требует всего O(1) дополнительной памяти (если дерево организовывать так, как показано выше).

Недостатки

  • Сложен в реализации.
  • Неустойчив — для обеспечения устойчивости нужно расширять ключ.
  • На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
  • На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.
  • Методу требуется «мгновенный» прямой доступ; не работает на связанных списках и других структурах памяти последовательного доступа.

Сортировка слиянием при расходе памяти O(n) быстрее (O(n\cdot\log n) с меньшей константой) и не подвержена деградации на неудачных данных.

Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.

Пример[править | править вики-текст]

C#:

static void HeapSort(int[] a)
{
    int i;
    int temp;

    for (i = a.Length / 2 - 1; i >= 0; i--)
    {
        shiftDown(a, i, a.Length);
    }

    for (i = a.Length - 1; i >= 1; i--)
    {
        temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        shiftDown(a, 0, i);
    }
}

static void shiftDown(int[] a, int i, int j)
{
    bool done = false;
    int maxChild;
    int temp;

    while ((i * 2 + 1 < j) && (!done))
    {
        if (i * 2 + 1 == j - 1)
            maxChild = i * 2 + 1; 
        else if (a[i * 2 + 1] > a[i * 2 + 2])
            maxChild = i * 2 + 1;
        else
            maxChild = i * 2 + 2;

        if (a[i] < a[maxChild])
        {
            temp = a[i];
            a[i] = a[maxChild];
            a[maxChild] = temp;
            i = maxChild;
        }
        else
        {
            done = true;
        }
    }
}

D:

void HeapSort(uint[] a)
 {
  int i;
  int temp;
  int len = a.length;
  for (i = len/ 2 - 1; i >= 0; i--)
   {
    ShiftDown(a, i, len);
   }
  for (i = len - 1; i > 0; i--)
   {
    temp = a[0];
    a[0] = a[i];
    a[i] = temp;
    ShiftDown(a, 0, i);
   }
 }
 
void ShiftDown(uint[] a, int i, int j)
 {
  uint temp;
  uint left = 2 * i + 1;
  uint right = left + 1;
  uint MaxChild = left;
  while (MaxChild < j)
   {
    if (right < j)
     {
      if (a[left] < a[right])
       {
        MaxChild = right;
       }
     }
    if (a[i] < a[MaxChild])
     {
      temp = a[i];
      a[i] = a[MaxChild];
      a[MaxChild] = temp;
     }
    else
     {
      break;
     }
    i = MaxChild;
    left = 2 * i + 1;
    right = left + 1;
    MaxChild = left;
   }
 }

Delphi(Pascal):

Procedure HeadSort(var a: array of Integer);
var
  i,temp,len: Integer;
  procedure ShiftDown(var a: array of Integer; i,j: integer);
  var
    Left,Right,MaxChild,temp: Integer; 
  begin
    left:=2*i+1;
    right:=left+1;
    MaxChild:=left;
    while MaxChild < j do 
    begin
      if Right < j then
      begin
        if a[left] < a[right] then MaxChild:=right;
        if a[i]<a[MaxChild] then 
        begin
          temp:=a[i];
          a[i]:=a[MaxChild];
          a[MaxChild]:=temp;
        end;
      end
      else break;
      i:=MaxChild;
      left:=2*i+1;
      right:=left+1;
      MaxChild:=left;
    end;
  end;
begin
  len:=Length(a);
  for i:=Round(len/2)-1 Downto 0 do 
    ShiftDown(a,i,len);
 
  for i:=len-1 DownTo 1 Do 
  begin
    temp:=a[0];
    a[0]:=a[i];
    a[i]:=temp;
    ShiftDown(a,0,i);
  end;
end;

Применение[править | править вики-текст]

Алгоритм "сортировка кучей" активно применяется в ядре Linux.

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • Ананий В. Левитин. Глава 6. Метод преобразования: Пирамиды и пирамидальная сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 275-284. — ISBN 5-8459-0987-2.
  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 6. Пирамидальная сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 182-188. — ISBN 5-8459-0857-4.

Ссылки[править | править вики-текст]