Sortowanie przez kopcowanie

Sortowanie przez kopcowanie

Sortowanie przez kopcowanie (ang. heapsort) to algorytm sortowania o złożoności czasowej O(n log n) i pamięciowej O(n). Mimo iż jest algorytmem niestabilnym, charakteryzuje się dobrą efektywnością i niskim poborem pamięci, co czyni go odpornym na ataki wykorzystujące celowo spreparowane dane.

Opis algorytmu

Algorytm oparty jest na strukturze danych zwanej binarnym kopcem zupełnym, co umożliwia efektywne operacje wstawiania i usuwania elementów. Proces sortowania składa się z dwóch głównych faz:

• Tworzenie kopca
• Sortowanie

Tworzenie kopca

W pierwszej fazie algorytm reorganizuje elementy tablicy, aby utworzyć kopiec. Można to zrobić, wykorzystując tę samą tablicę, co zapewnia stałą złożoność pamięciową. Istnieją dwie metody budowy kopca:

• Rozbudowa kopca o każdy element z tablicy, co wymaga czasu O(n log n).
• Budowa kopca w czasie O(n) przez zastosowanie procedury shift-down dla pierwszych n/2 elementów.

Sortowanie

Po utworzeniu kopca następuje faza sortowania, polegająca na usuwaniu elementu maksymalnego z kopca i wstawieniu go na koniec tablicy. Proces ten powtarza się do momentu, gdy wszystkie elementy zostaną posortowane. Złożoność tej fazy również wynosi O(n log n).

Implementacja

Algorytm można zaimplementować w różnych językach programowania. Poniżej znajduje się przykład w Pascalu:

{$APPTYPE CONSOLE}
type
  TElem = integer;
const
  Size = 13;
var
  T: array[1..Size] of TElem = (4, 1, 3, 2, 16, 9, 10, 14, 8, 7, 99, 78, 55);

procedure shift_down(n, i: integer);
begin
  // Implementacja procedury shift-down
end;

procedure build_heap;
begin
  // Implementacja budowy kopca
end;

procedure sort;
begin
  // Implementacja sortowania
end;

begin
  build_heap;
  sort;
end.

Porównanie z innymi algorytmami sortowania

Heapsort jest zazwyczaj wolniejszy od sortowania szybkiego (quicksort), ale ma lepszą złożoność pesymistyczną O(n log n) w porównaniu do O(n²) dla quicksort. W porównaniu do sortowania przez scalanie (mergesort), heapsort jest nieco wolniejszy, ale wymaga mniej pamięci dodatkowej.

W związku z tym, heapsort jest korzystnym wyborem w sytuacjach, gdzie pamięć jest ograniczona lub kiedy rozmiar danych jest duży.