Twoje Centrum Szkoleniowe

C++: Sortowanie przez kopcowanie (Heap Sort)

Sortowanie przez kopcowanie, znane również jako heap sort, to wydajny algorytm sortujący opierający się na strukturze danych zwaną kopcem. Idea tego algorytmu polega na organizacji nieuporządkowanych danych w strukturę typu kopiec binarny, co pozwala na efektywne sortowanie elementów. Kopiec to specjalny rodzaj drzewa binarnego, gdzie każdy węzeł nadrzędny ma wartość większą (lub mniejszą, w zależności od typu kopca) od swoich węzłów potomnych. Sortowanie przez kopcowanie wykorzystuje właściwości kopca do przekształcania nieposortowanej tablicy danych w uporządkowany zestaw wartości.

Algorytm sortowania przez kopcowanie został opracowany w latach 60. XX wieku przez informatyka J.W.J. Williamsa.

 

 

Zasada działania sortowania przez kopcowanie

 

Budowa Kopca

Kluczowym elementem sortowania przez kopcowanie jest proces tworzenia kopca binarnego z nieuporządkowanych danych. Kopiec binarny to specyficzna struktura danych, która w kontekście tego algorytmu może przyjąć formę kopca maksymalnego lub minimalnego. W kopcu maksymalnym każdy węzeł nadrzędny ma wartość większą od swoich dzieci, natomiast w kopcu minimalnym – mniejszą. Proces tworzenia kopca rozpoczyna się od najniższego poziomu drzewa, stopniowo przesuwając się w górę. Dla każdego węzła sprawdzane jest, czy spełnia on warunek kopca; jeśli nie, jest on zamieniany z większym (lub mniejszym, w zależności od typu kopca) z dzieci, a następnie proces jest powtarzany rekurencyjnie dla zamienionego węzła.

 

Proces Sortowania

Gdy kopiec jest już zbudowany, algorytm przechodzi do fazy sortowania. Pierwszym krokiem jest usunięcie korzenia kopca (największego lub najmniejszego elementu, w zależności od typu kopca) i zamiana go z ostatnim elementem. Następnie kopiec jest „przywracany” poprzez rekurencyjne zamienianie nowego korzenia z jego większym dzieckiem, aż do momentu, gdy wszystkie warunki kopca zostaną spełnione. Usunięty pierwotnie korzeń jest umieszczany na końcu tablicy, co oznacza jego ostateczne posortowanie. Proces ten jest powtarzany aż do momentu, gdy wszystkie elementy zostaną usunięte z kopca i umieszczone w posortowanej tablicy.

Sortowanie przez kopcowanie jest wydajne, ponieważ wykorzystuje własności kopca do minimalizowania liczby porównań i zamian potrzebnych do uporządkowania danych. Ta metoda jest szczególnie skuteczna dla dużych zbiorów danych, oferując stabilną i przewidywalną wydajność niezależnie od początkowego rozkładu elementów w tablicy.

 

 

Implementacja Sortowania przez Kopcowanie w C++

Implementacja algorytmu sortowania przez kopcowanie w języku C++ wymaga zrozumienia, jak działa kopiec binarny i jak można go wykorzystać do sortowania danych. Proces ten składa się z kilku kluczowych kroków:

1. Tworzenie Kopca: Pierwszym krokiem jest przekształcenie tablicy danych w kopiec binarny. To osiąga się przez porównanie elementów i przekształcenie struktury danych tak, aby spełniała warunki kopca maksymalnego lub minimalnego.
2. Sortowanie Elementów: Po utworzeniu kopca, algorytm systematycznie usuwa elementy z kopca, zaczynając od korzenia (największego lub najmniejszego elementu, w zależności od typu kopca), i umieszcza je w odpowiednim miejscu w tablicy. Każde usunięcie elementu wymaga reorganizacji kopca, aby nadal spełniał on swoje podstawowe właściwości.
3. Powtarzanie Procesu: Proces jest powtarzany, aż wszystkie elementy zostaną usunięte z kopca i posortowane w tablicy.

 

Poniżej znajduje się przykładowy kod realizujący algorytm sortowania przez kopcowanie w C++:

#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i) {
    int largest = i; 
    int left = 2 * i + 1; 
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    cout << "Sorted array is \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

 

Analiza kodu

1. Funkcja heapify:

   • Parametry:
     • arr[]: Tablica do kopcowania.
     • n: Rozmiar kopca.
     • i: Indeks węzła, który jest obecnie 'kopcowany'.
   • Zmienne w funkcji:
     • largest: Przechowuje indeks największego elementu pomiędzy bieżącym węzłem, jego lewym i prawym dzieckiem.
     • left: Indeks lewego dziecka węzła i.
     • right: Indeks prawego dziecka węzła i.
   • Przebieg funkcji:
     • Funkcja porównuje wartość węzła i z wartościami jego dzieci. Jeśli któreś dziecko ma większą wartość, to largest jest aktualizowane.
     • Jeśli largest nie jest równy i, wskazuje to, że któreś z dzieci ma większą wartość. Węzły i i largest są zamieniane miejscami, a następnie heapify jest rekurencyjnie wywoływana dla poddrzewa o korzeniu w largest.

2. Funkcja heapSort:

   • Parametry:
     • arr[]: Tablica do posortowania.
     • n: Rozmiar tablicy.
   • Budowa kopca:
     • Początkowo budowany jest kopiec. Pętla for zaczyna się od ostatniego 'rodzica' w kopcu i idzie wstecz, wywołując heapify dla każdego węzła. To tworzy kopiec maksymalny.
   • Proces sortowania:
     • Następnie elementy są usuwane z kopca poprzez zamianę pierwszego elementu kopca (największego) z ostatnim elementem kopca, a następnie 'kopcowanie' reszty kopca. Każda iteracja pętli for zmniejsza rozmiar kopca o jeden, ponieważ ostatni element jest już na swoim miejscu.

3. Funkcja main:

   • Tworzy tablicę arr i oblicza jej rozmiar n.
   • Wywołuje heapSort dla tej tablicy.
   • Wyświetla posortowaną tablicę.
4. Funkcja swap jest używana do zamiany elementów w tablicy.

 

Optymalizacje i warianty algorytmu sortowania przez kopcowanie

 

Metody optymalizacji

Sortowanie przez kopcowanie jest efektywnym algorytmem, ale istnieją sposoby na jego usprawnienie, zwłaszcza w kontekście specyficznych zastosowań lub ograniczeń zasobów. Oto kilka technik, które mogą poprawić jego wydajność:

1. Optymalizacja procesu tworzenia kopca: Jednym z kluczowych elementów jest efektywne tworzenie kopca. Optymalizacja tej części, na przykład poprzez zmniejszenie liczby operacji zamiany elementów, może znacząco skrócić czas sortowania.
2. Wybór metody kopcowania: Tradycyjnie stosowane są kopce maksymalne, ale w niektórych przypadkach kopiec minimalny może być bardziej efektywny, w zależności od rodzaju danych i wymagań końcowego uporządkowania.
3. Zmniejszenie złożoności przestrzennej: W niektórych implementacjach sortowania przez kopcowanie można ograniczyć zużycie dodatkowej pamięci, wykonując sortowanie "na miejscu" bez konieczności tworzenia dodatkowych struktur danych.

 

Inne wersje kopcowania

Sortowanie przez kopcowanie jest elastycznym algorytmem, który pozwala na różne adaptacje i modyfikacje. Oto niektóre z nich:

1. Sortowanie przez kopcowanie zwiększające (Increasing Heap Sort): Ta odmiana sortowania przez kopcowanie polega na budowaniu kopca minimalnego, co powoduje, że najmniejsze elementy są usuwane jako pierwsze. Jest to szczególnie przydatne, gdy wymagane jest posortowanie danych w porządku rosnącym.
2. Sortowanie przez kopcowanie z użyciem list: W niektórych implementacjach sortowania przez kopcowanie można wykorzystać listy zamiast tradycyjnych tablic. Choć to podejście może być mniej wydajne pod względem czasowym, oferuje większą elastyczność w zarządzaniu pamięcią.
3. Hybrydowe metody sortowania: Sortowanie przez kopcowanie można łączyć z innymi algorytmami sortowania, takimi jak sortowanie szybkie, aby uzyskać optymalne wyniki w zależności od charakterystyki danych i wymagań wydajnościowych.

Każda z tych metod ma swoje unikalne zalety i może być stosowana w różnych scenariuszach, w zależności od specyficznych wymagań i ograniczeń danego problemu. Wybór odpowiedniej metody optymalizacji lub wariantu algorytmu jest kluczowy dla osiągnięcia optymalnej wydajności.

 

Analiza złożoności algorytmu sortowania przez kopcowanie

 

Złożoność czasowa i przestrzenna

Sortowanie przez kopcowanie to efektywny algorytm sortujący, którego zrozumienie wymaga analizy jego złożoności zarówno czasowej, jak i przestrzennej:

1. Złożoność czasowa: Główną siłą tego algorytmu jest jego złożoność czasowa, która w większości przypadków wynosi O(n log n). Oznacza to, że czas potrzebny do wykonania sortowania zwiększa się logarytmicznie wraz ze wzrostem liczby elementów. Jest to efektywność porównywalna z innymi zaawansowanymi algorytmami sortującymi.
2. Złożoność przestrzenna: Sortowanie przez kopcowanie można zrealizować "na miejscu", co oznacza, że nie wymaga dodatkowej pamięci poza wejściową tablicą. Ta właściwość czyni go atrakcyjnym wyborem w sytuacjach, gdzie dostępna pamięć jest ograniczona.

 

Praktyczne zastosowania i ograniczenia sortowania przez kopcowanie

 

Kiedy wybrać sortowanie przez kopcowanie

Sortowanie przez kopcowanie, ze względu na swoje unikalne cechy, jest szczególnie przydatne w określonych warunkach i scenariuszach:

1. Duże zbiory danych: Algorytm ten jest efektywny przy sortowaniu dużych zbiorów danych, dzięki swojej stabilnej złożoności czasowej O(n log n).
2. Ograniczona pamięć: Jako algorytm sortujący "na miejscu", sortowanie przez kopcowanie jest idealne w środowiskach, gdzie dostępna pamięć jest ograniczona. Nie wymaga dodatkowej przestrzeni, co jest dużą zaletą w porównaniu do niektórych innych algorytmów, takich jak sortowanie przez scalanie.
3. Wymaganie stabilnej wydajności: Sortowanie przez kopcowanie ma przewidywalną wydajność niezależnie od początkowego uporządkowania danych wejściowych, co jest korzystne w systemach wymagających konsekwentnego czasu wykonania.

 

Ograniczenia algorytmu

Mimo swoich zalet, sortowanie przez kopcowanie posiada również ograniczenia, które warto rozważyć przy wyborze algorytmu sortującego:

1. Mniej efektywne na niektórych zestawach danych: W praktyce sortowanie przez kopcowanie może okazać się mniej efektywne niż inne algorytmy, takie jak sortowanie szybkie, szczególnie na małych lub częściowo posortowanych zestawach danych.
2. Brak stabilności: Sortowanie przez kopcowanie nie jest stabilnym algorytmem, co oznacza, że identyczne elementy mogą nie zachować swojej pierwotnej kolejności po sortowaniu.
3. Złożoność implementacji: Dla początkujących programistów implementacja sortowania przez kopcowanie może być bardziej skomplikowana niż prostsze algorytmy, takie jak sortowanie bąbelkowe czy przez wstawianie.

Sortowanie przez kopcowanie stanowi efektywne narzędzie w arsenale programisty, szczególnie gdy wymagana jest efektywność w zarządzaniu dużymi zbiorami danych lub ograniczeniach pamięciowych. Jednakże, należy dokładnie rozważyć charakter danych i wymagania aplikacji przed jego wyborem, aby w pełni wykorzystać jego potencjał i uniknąć potencjalnych ograniczeń.