Пірамідальне сортування
Пірамідальне сортування (англ. Heapsort, «Сортування купою») — алгоритм сортування, працює гарантовано за Θ(n log n) операцій при сортуванні n елементів. Кількість застосовуваної службової пам'яті не залежить від розміру масиву (тобто, O(1)).
 Приклад сортування випадкового набору чисел за алгоритмом пірамідальне сортування. | |
| Клас | Алгоритм сортування |
|---|---|
| Структура даних | масив |
| Найгірша швидкодія | |
| Найкраща швидкодія | [1] |
| Середня швидкодія | |
| Просторова складність у найгіршому випадку | основний, допоміжний |
| Оптимальний | Інколи |
| Стабільний | Нестійка |
Опис алгоритму
Приклад сортувального дерева
Структура зберігання даних сортувального дерева
Сортування пірамідою використовує бінарне сортувальне дерево. Сортувальне дерево — це таке дерево, у якого виконані умови:
- Кожен лист має глибину або , або , де — максимальна глибина дерева;
- Значення в будь-якій вершині не менші (інший варіант — не більші) за значення їх нащадків.
Зручна структура даних для сортувального дерева — такий масив 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 <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;
}
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.
Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.