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

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

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

Опис алгоритму[ред.ред. код]

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

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

  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 <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(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)

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.

Примітки[ред.ред. код]

Посилання[ред.ред. код]