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

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

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

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

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

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

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

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

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

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

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

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

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

при .

Этот шаг требует операций.

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(1) дополнительной памяти (если дерево организовывать так, как показано выше).

Недостатки

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

Сортировка слиянием при расходе памяти O(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 HeapSort(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 ShiftDown(T a[], int i, int j)
{
	int MaxNodeId;
	bool ShiftDone = false;
	while (((i * 2 + 1) < j) && !ShiftDone)
	{
		if (i * 2 + 1 == j - 1 || a[i * 2 + 1] > a[i * 2 + 2])
		{
			MaxNodeId = i * 2 + 1;
		}
		else
		{
			MaxNodeId = i * 2 + 2;
		}

		if (a[i] < a[MaxNodeId])
		{
			std::swap(a[i], a[MaxNodeId]);
			i = MaxNodeId;
		}
		else
		{
			ShiftDone = true;
		}
	}
}

template <typename T>
void HeapSort(T a[], int l)
{
	int i;
	//Строим дерево поиска
	for (i = (l / 2) - 1; i > -1; i--)
	{
		ShiftDown(a, i, l);
	}

	//Забираем максимальный (0) элемент дерева в i-ю позицию
	//Перемещаем новый 0 элемент на правильную позицию в дереве
	for (i = l - 1; i > 0; i--)
	{
		std::swap(a[0], a[i]);
		ShiftDown(a, 0, i);
	}
}

Python:

def HeapSort(a):
    def shiftDown(a,i,j):
        while i*2+1<j:
            if i*2+1==j-1 or a[i*2+1]>a[i*2+2]:
                maxChild=i*2+1
            else:
                maxChild=i*2+2
            if a[i]<a[maxChild]:
                a[i],a[maxChild]=a[maxChild],a[i]
                i=maxChild
            else:break
    for i in range(int(len(a)/2-1),-1,-1):
        shiftDown(a,i,len(a))
    for i in range(len(a)-1,0,-1):
        a[0],a[i]=a[i],a[0]
        shiftDown(a,0,i)

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

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

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

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

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