Пірамідальне сортування

Пірамідальне сортування

Приклад сортування випадкового набору чисел за алгоритмом пірамідальне сортування. Приклад сортування випадкового набору чисел за алгоритмом пірамідального сортування.
Клас	Алгоритм сортування
Структура даних	масив
Найгірша швидкодія	$O(n\log n)$
Найкраща швидкодія	$\Omega (n),O(n\log n)$
Середня швидкодія	$O(n\log n)$
Просторова складність у найгіршому випадку	$O(n)$ основний, $O(1)$ допоміжний
Оптимальний	Інколи
Стабільний	Нестійка

Пірамідальне сортування (англ. Heapsort, «Сортування купою») — алгоритм сортування, працює гарантовано за Θ(n log n) операцій при сортуванні n елементів. Кількість застосовуваної службової пам'яті не залежить від розміру масиву (тобто, O(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\log n)$;
• вимагає $O(1)$ додаткової пам'яті.

Недоліки алгоритму

• нестійкий — для забезпечення стійкості потрібно розширювати ключ;
• на майже відсортованих даних працює так само довго, як і на хаотичних даних;
• складний в реалізації;
• на одному кроці вибірку доводиться робити хаотично по всій довжині масиву — тому алгоритм погано поєднується з кешуванням і (рос. "файлом підкачки", укр. "файлом довантаження") ― віртуальної пам'яті;
• методу потрібно «миттєвий» прямий доступ; не працює на зв'язаних списках та інших структурах пам'яті послідовного доступу.

Приклади реалізації

C++

 #include <iostream>
 #include <cmath>
 
 using namespace std;
 
 void RestoreHeap(int m[], int father, int last_N)
 {
 	while(father<=last_N/2)
 	{
 		int maxson=2*father;
 		if (2*father+1<=last_N && m[2*father]<m[2*father+1]) maxson=2*father+1;
 		if (m[maxson]>m[father])
 		{
                 swap(m[maxson],m[father]);
                 father=maxson;
 		}
 		else return;
 
 	}
 }
 void HeapSort(int m[], int N)
 {
 	for (int i=N/2; i>=1; i--)
 		RestoreHeap(m,i,N);
 	for (int i=N; i>1; i--)
 	{
 		swap(m[1],m[i]);
 		RestoreHeap(m,1,i-1);
 	}
 }
 void read_mas(int m[],int &N)
     {
         cin >> N;
         for(int i=1;i<=N;i++)
         cin >> m[i];
     }
 void write_mas(int m[],int N)
 {
         for(int i=1;i<=N;i++)
         cout << m[i] << " ";
 }
 int main()
 {
     int m[100000],N;
     read_mas(m,N);
     HeapSort(m,N);
     write_mas(m,N);
     return 0;
 }

Java

import java.util.Arrays;

public class HeapSort {

    public static void main(final String[] args) {
        final int[] a = { 3,4,5,6,2,23,567,9,1,4,0 };
        System.out.println(Arrays.toString(a));
        heapSort(a, a.length);
        System.out.println(Arrays.toString(a));
    }

    private static void heapSort(final int[] array, final int count) {
        heapify(array, count);

        int end = count - 1;
        while (end > 0) {
            swap(array, end, 0);
            siftDown(array, 0, --end);
        }
    }

    private static void swap(final int[] array, final int a, final int b) {
        final int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    private static void heapify(final int[] array, final int count) {
        int start = count / 2 - 1;

        while (start >= 0) {
            siftDown(array, start, count - 1);
            start--;
        }
    }

    private static void siftDown(final int[] array, final int start, final int end) {
        int root = start;

        while (root * 2 + 1 <= end) {
            int child = root * 2 + 1;
            int swap = root;
            if (array[swap] < array[child]) {
                swap = child;
            }
            if (child + 1 <= end && array[swap] < array[child + 1]) {
                swap = child + 1;
            }
            if (swap != root) {
                swap(array, root, swap);
                root = swap;
            } else {
                return;
            }
        }
    }
}

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(round(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)
    return li

Delphi

program Heap_sort_v2;
{$APPTYPE CONSOLE}
uses
  SysUtils;

type
  aint=array [1..20] of integer;

var
  Arr:aint; 
  n:integer;

procedure change(var a, b:integer);
var
  tmp:integer;
begin
  tmp:=a;
  a:=b;
  b:=tmp;
end;

procedure rebuild(var A2:aint; f,d:word);
var
  MaxSon:word;
begin
  MaxSon:=f;
  if (2*f<=d)and(A2[Maxson]<a2[2*f]) then
    MaxSon:=2*f;
  if (2*f+1<=d)and(A2[MaxSon]<A2[2*f+1]) then
    MaxSon:=2*f+1;
  if MaxSon<>f then
  begin
    change(A2[f],A2[MaxSon]);
    rebuild(A2,MaxSon,d);
  end;
end;

procedure build (var A3:aint; n3:word);
var
  j:word;
begin
  for j:=n3 div 2 downto 1 do
    rebuild(a3,j,n3);
end;

procedure heapsort(var A1:aint; n1:word);
var
  j:word;
begin
  build(a1,n1);
  for j:=n1 downto 2 do
  begin
    change(A1[1],A1[j]);
    rebuild(A1,1,j-1);
  end
end;

procedure RndArrInput(var A4:aint; n4:word);
var
  i:word;
begin
  Randomize;
  for i:=1 to n4 do
    a4[i]:=random(10)-5;
end;

Procedure ArrOutput(var A5:aint; n5:word);
var
  i:word;
begin
  for i:=1 to n5 do
    write(a5[i],' ');
end;

begin
  Writeln('enter data');
  readln(n);
  RndArrInput(arr,n);
  ArrOutput(arr,n);
  heapsort(arr,n);
  readln;
  Arroutput(arr,n);
  writeln('that''s all');
  readln;
end.

Посилання

• Animated Sorting Algorithms: Heap Sort — графічна демонстрація роботи алгоритму
• Heapsort
• Heapsort animated
• NIST's Dictionary of Algorithms and Data Structures: Heapsort
• Sorting revisited
• Java-based demonstration of Heapsort
• A colored graphical Java applet
• Хабрахабр — опис сортування купою