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

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

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

Пірамідальне сортування (англ. Heapsort, «Сортування купою») — алгоритм сортування, працює гарантовано за Θ(n log n) операцій при сортуванні n елементів. Кількість застосовуваної службової пам'яті не залежить від розміру масиву (тобто, O(1)).

Сортування пірамідою використовує бінарне сортувальне дерево. Сортувальне дерево — це таке дерево, у якого виконані умови:

1. Кожен лист має глибину або ${\displaystyle d}$, або ${\displaystyle d-1}$, де ${\displaystyle d}$ — максимальна глибина дерева;
2. Значення в будь-якій вершині не менші (інший варіант — не більші) за значення їх нащадків.

Зручна структура даних для сортувального дерева — такий масив Array, що Array[1] — елемент в корені, а нащадки елемента Array[i] є Array[2i] і Array[2i+1].

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

1. Вибудовуємо елементи масиву у вигляді сортувального дерева:

${\displaystyle {\text{Array}}[i]\geq {\text{Array}}[2i]}$

${\displaystyle {\text{Array}}[i]\geq {\text{Array}}[2i+1]}$

при ${\displaystyle 1\leq i<n/2}$

Цей крок вимагає ${\displaystyle 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] — впорядкована послідовність.

Цей крок вимагає ${\displaystyle O(n\log n)}$ операцій.

• час роботи в найгіршому випадку — ${\displaystyle O(n\log n)}$;
• вимагає ${\displaystyle O(1)}$ додаткової пам'яті.

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

 #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;  } 

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;             }         }     } } 

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 

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
• Хабрахабр — опис сортування купою