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

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

Пирамидальная сортировка (англ. 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;
      end;
      if a[i]<a[MaxChild] then
      begin
       temp:=a[i];
       a[i]:=a[MaxChild];
       a[MaxChild]:=temp;
      end;
      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;

C++:

template <typename T>
void shift_down( T& a, int i, int j)
{
    bool done = false;
    int maxChild;

    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])
        {
            std::swap( a[i], a[maxChild]);
            i = maxChild;
        }
        else
            done = true;
    }
}

template <typename T>
void heapsort( T& a)
{
	int i;
	typename T::size_type size = a.size();

	for (i = size / 2 - 1; i >= 0; i--)
		shift_down(a, i, size);

	for (i = size - 1; i >= 1; i--)
	{
		std::swap( a[0], a[i]);
		shift_down( a, 0, i);
	}
}

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

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

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

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

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