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

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

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

Пирамидальная сортировка — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(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).
• Требует всего O(1) дополнительной памяти (если дерево организовывать так, как показано выше).

Недостатки

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

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

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

[править] Примеры реализации

[править] C++

#include <iterator>
 
template< typename Iterator >
void adjust_heap( Iterator first
                  , typename std::iterator_traits< Iterator >::difference_type current
                  , typename std::iterator_traits< Iterator >::difference_type size
                  , typename std::iterator_traits< Iterator >::value_type tmp )
{
    typedef typename std::iterator_traits< Iterator >::difference_type diff_t;
 
    diff_t top = current, next = 2 * current + 2;
 
    for ( ; next < size; current = next, next = 2 * next + 2 )
    {
        if ( *(first + next) < *(first + next - 1) )
            --next;
        *(first + current) = *(first + next);
    }
 
    if ( next == size )
        *(first + current) = *(first + size - 1), current = size - 1;
 
    for ( next = (current - 1) / 2;
          top > current && *(first + next) < tmp;
          current = next, next = (current - 1) / 2 )
    {
        *(first + current) = *(first + next);
    }
    *(first + current) = tmp;
}
 
template< typename Iterator >
void pop_heap( Iterator first, Iterator last)
{
    typedef typename std::iterator_traits< Iterator >::value_type value_t;
 
    value_t tmp = *--last;
    *last = *first;
    adjust_heap( first, 0, last - first, tmp );
}
 
template< typename Iterator >
void heap_sort( Iterator first, Iterator last )
{
    typedef typename std::iterator_traits< Iterator >::difference_type diff_t;
    for ( diff_t current = (last - first) / 2 - 1; current >= 0; --current )
        adjust_heap( first, current, last - first, *(first + current) );
 
    while ( first < last )
        pop_heap( first, last-- );
}

[править] 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 0 do begin
    Current := Arr[i]; //перемещаем верхушку в начало отсортированного списка
    Arr[i] := Arr[0];
    DownHeap(0, i, Current); //находим нужное место в пирамиде для нового элемента
  end;
end;

[править] Pascal (другой вариант)

Примечание: myarray = array[1..Size] of integer; N — количество элементов массива

procedure HeapSort(var m: myarray; N: integer);
var
  i: integer;
 
  procedure Swap(var a,b:integer);
  var
    tmp: integer;
  begin
    tmp:=a;
    a:=b;
    b:=tmp;
  end;
 
  procedure Sort(Ns: integer);
  var
    i, tmp, pos, mid: integer;
  begin
    mid := Ns div 2;
    for i := mid downto 1 do
    begin
      pos := i;
      while pos<=mid do
      begin
        tmp := pos*2;
        if tmp<Ns then
        begin
          if m[tmp+1]<m[tmp] then
            tmp := tmp+1;
          if m[pos]>m[tmp] then
          begin
            Swap(m[pos], m[tmp]);
            pos := tmp;
          end
          else
            pos := Ns;
        end
        else
          if m[pos]>m[tmp] then
          begin
            Swap(m[pos], m[tmp]);
            pos := Ns;
          end
          else
            pos := Ns;
        end;
      end;
    end;
begin
  for i:=N downto 2 do
  begin
    Sort(i);
    Swap(m[1], m[i]);
  end;
end;

[править] Python

def heapSort(li):
    """Сортирует список в возрастающем порядке с помощью алгоритма пирамидальной сортировки"""
 
    def downHeap(li, k, n):
        new_elem = li[k]
        while k <= n/2:
            child = 2*k;
            if child < n and li[child] < li[child+1]:
                child += 1
            if new_elem >= li[child]:
                break
            li[k] = li[child]
            k = child
        li[k] = new_elem
 
    size = len(li)
    for i in range(size/2-1,-1,-1):
        downHeap(li, i, size-1)
    for i in range(size-1,0,-1):
        temp = li[i]
        li[i] = li[0]
        li[0] = temp
        downHeap(li, 0, i-1)

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

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

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

• Пирамидальная сортировка — подробное описание с иллюстрациями и примерами. Приведён вывод оценок скорости работы алгоритма и измерение времени работы на реальной вычислительной системе.