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

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

Пірамідальне сортування – алгоритм сортування на основі порівнянь. Хоча, на практиці, він трохи повільніший на більшості машин, ніж швидке сортування, у нього є перевага – швидкодія у найгіршому випадку рівна (n log n). Є не стабільним алгоритмом.

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

Нехай A[1 .. n] — деякий масив. Зіставимо йому дерево, використовуючи такі правила:

1. A[1] - корінь дерева.
2. Якщо A[i] - вузол дерева і 2i , то A[2*i] - вузол - “лівий син” вузла A[i].
3. Якщо A[i] - вузол дерева і 2i + 1 , то A[2*i+1] - вузол - “правий син” вузла A[i].

Правила 1-3 визначають у масиві структуру дерева, причому глибина дерева не перевершує [log2 n] + 1. Вони ж задають спосіб руху по дереву від кореня до листків. Рух вгору задається правилом 4:

4. Якщо A[i] - вузол дерева та i > 1, то A[i mod 2] - вузол - «батько» вузла A[i];

Приклади реалізації[ред.ред. код]

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.

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

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