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

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

Приклад сортування випадкового набору чисел за алгоритмом пірамідального сортування.
Клас	Алгоритм сортування
Структура даних	масив
Найгірша швидкодія	${\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)).

Ця стаття потребує упорядкування для відповідності стандартам якості Вікіпедії. Будь ласка, допоможіть поліпшити цю статтю. Можливо, сторінка обговорення містить зауваження щодо потрібних змін. (Дізнайтеся, як і коли вилучати це шаблонне повідомлення[en])

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

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