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

Материал из Википедии — свободной энциклопедии

Анимированная схема алгоритма

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

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

[править] Алгоритм

пример сортирующего дерева

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

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

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

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

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

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

при .

Этот шаг требует 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(nlogn) операций.

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

Достоинства

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

Недостатки

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

[править] Код на C++

template<class T>
void downHeap( T a[], int k, int n )
{
//  процедура просеивания следующего элемента
//  До процедуры: a[k+1]...a[n]  - пирамида
//  После:  a[k]...a[n]  - пирамида
   T new_elem = a[ k ];
// пока у a[k] есть дети
   while( k <= n / 2 )
   {
      int child = 2 * k;
  //  выбираем большего сына
      if( child < n && a[ child ] < a[ child + 1 ] )
         child++;
      if( new_elem >= a[ child ] )
         break;
   // иначе переносим сына наверх
      a[ k ] = a[ child ];
      k = child;
   }
   a[ k ] = new_elem;
}
 
template<class T>
void heapSort( T a[], int size )
{
// строим пирамиду
   for( int i = size / 2 - 1; i >= 0; i-- )
   {
      downHeap( a, i, size - 1 );
   }
// теперь a[0]...a[size-1] пирамида
   for( int i = size - 1; i > 0; i-- )
   {
   // меняем первый с последним
      T temp = a[ i ];
      a[ i ] = a[ 0 ];
      a[ 0 ] = temp;
   // восстанавливаем пирамидальность a[0]...a[i-1]
      downHeap( a, 0, i - 1 );
   }
}

[править] Код на Pascal

Вместо "SomeType" подставьте любой из арифметических типов (например integer)

procedure Sort(var Arr: array of SomeType; Count: Integer);
 
  procedure DownHeap(index, Count: integer; Current: SomeType);
  //Функция пробегает по пирамиде восстанавливая ее
  //Также используется для изначального создания пирамиды
  //Использование: Передать номер следующего элемента в index
  //Процедура пробежит по всем потомкам и найдет нужное место для следующего элемента
  var
    Child: Integer;
  begin
    while index < Count div 2 do begin
      Child := (index+1)*2-1;
      if (Child < Count-1) and (Arr[Child] < Arr[Child+1]) then
        Child:=Child+1;
      if Current >= Arr[Child] then
        break;
      Arr[index] := Arr[Child];
      index := Child;
    end;
    Arr[index] := Current;
  end;
 
//Основная функция
var
  i: integer;
  Current: SomeType;
begin
  //Собираем пирамиду
  for i := (Count div 2)-1 downto 0 do
    DownHeap(i, Count, Arr[i]);
  //Пирамида собрана. Теперь сортируем
  for i := Count-1 downto 1 do begin
    Current := Arr[i]; //перемещаем верхушку в начало отсортированного списка
    Arr[i] := Arr[0];
    DownHeap(0, i, Current); //находим нужное место в пирамиде для нового элемента
  end;
end;

[править] Литература

• Ананий В. Левитин Глава 6. Метод преобразования: Пирамиды и пирамидальная сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 275-284. — ISBN 0-201-74395-7