Відкрити головне меню

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

Пірамідальне сортування
Приклад сортування випадкового набору чисел за алгоритмом пірамідальне сортування.
Приклад сортування випадкового набору чисел за алгоритмом пірамідального сортування.
Клас Алгоритм сортування
Структура даних масив
Найгірша швидкодія
Найкраща швидкодія [1]
Середня швидкодія
Просторова складність у найгіршому випадку основний, допоміжний
Оптимальний Інколи
Стабільний Нестійка

Зміст

Опис алгоритмуРедагувати

 
Приклад сортувального дерева
 
Структура зберігання даних сортувального дерева

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

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

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

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

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

 

 

при  

Цей крок вимагає   операцій.

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] — впорядкована послідовність.

Цей крок вимагає   операцій.

Переваги та недолікиРедагувати

Переваги алгоритмуРедагувати

  • час роботи в найгіршому випадку —  ;
  • вимагає   додаткової пам'яті.

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

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

Приклади реалізаціїРедагувати

C++Редагувати

#include <algorithm> // для std::make_heap, std::sort_heap

template <typename Iterator>
void heap_sort(Iterator begin, Iterator end)
{
    std::make_heap(begin, end);
    std::sort_heap(begin, end);
}

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.

ПриміткиРедагувати

ПосиланняРедагувати