Sortowanie stogowe, znane również jako Heap Sort, to algorytm sortowania wykorzystujący specjalną strukturę danych nazywaną kopcem. Zamiast porównywać elementy jeden po drugim, algorytm najpierw układa dane w taki sposób, aby największa wartość znajdowała się na początku struktury. Następnie przenosi ją na koniec tablicy, przebudowuje pozostały fragment i powtarza całą operację. Brzmi trochę mniej intuicyjnie niż sortowanie przez wstawianie czy bąbelkowe, ale po prześledzeniu kilku kroków mechanizm Heap Sort staje się całkiem logiczny.
- Na czym polega sortowanie stogowe?
- Czym jest kopiec w Heap Sort?
- Heap Sort krok po kroku
- Przykład sortowania stogowego
- Sortowanie stogowe w Pythonie
- Jak działa kod Heap Sort?
- Złożoność obliczeniowa Heap Sort
- Zalety i wady sortowania stogowego
- Heap Sort a inne algorytmy sortowania
- FAQ - sortowanie stogowe
Na czym polega sortowanie stogowe?
Najłatwiej wyobrazić sobie Heap Sort jako ciągłe wybieranie największego elementu z tablicy. Różnica polega na tym, że algorytm nie szuka go za każdym razem od początku. Najpierw odpowiednio organizuje elementy, dzięki czemu największa wartość znajduje się w znanym miejscu.
W przypadku sortowania rosnącego budowany jest tak zwany kopiec maksymalny. Oznacza to, że na jego początku znajduje się największy element. Algorytm zamienia go miejscami z ostatnim elementem tablicy. Ten element można już uznać za ustawiony prawidłowo.
Następnie rozmiar obszaru wymagającego sortowania zostaje zmniejszony o jeden. Kopiec jest poprawiany, ponownie największa liczba trafia na początek i cały proces zaczyna się od nowa.
W efekcie największe wartości stopniowo wędrują na prawą stronę tablicy, aż wszystkie elementy znajdą się na swoich miejscach.
Czym jest kopiec w Heap Sort?
Słowo "kopiec" może początkowo sugerować coś skomplikowanego, ale chodzi po prostu o określony sposób organizacji elementów.
Kopiec można przedstawić jako drzewo binarne. W kopcu maksymalnym każdy rodzic ma wartość nie mniejszą niż jego dzieci. Dzięki temu największy element całej struktury znajduje się na samej górze.
Weźmy przykładową tablicę:
[10, 5, 8, 3, 4]
Można ją potraktować jak takie drzewo:
10
/ \
5 8
/ \
3 4
Wartość 10 jest większa od 5 i 8. Z kolei 5 jest większe od 3 i 4. Taka struktura spełnia więc warunek kopca maksymalnego.
Co ciekawe, w programie nie trzeba tworzyć osobnych obiektów drzewa. Całą strukturę można przechowywać w zwykłej tablicy.
Dla elementu znajdującego się pod indeksem i jego dzieci można znaleźć za pomocą wzorów:
lewe dziecko = 2 * i + 1 prawe dziecko = 2 * i + 2
Ta zależność pozwala obsługiwać kopiec bez dodatkowych struktur danych.
Heap Sort krok po kroku
Cały algorytm można podzielić na dwie większe części. Najpierw z nieuporządkowanej tablicy tworzymy kopiec maksymalny. Dopiero potem zaczyna się właściwe sortowanie.
- Utwórz kopiec maksymalny z elementów znajdujących się w tablicy.
- Zamień pierwszy element kopca z ostatnim elementem sortowanego fragmentu.
- Zmniejsz rozmiar kopca o jeden.
- Przywróć poprawną strukturę kopca.
- Ponownie przenieś największy element na koniec.
- Powtarzaj operację aż do posortowania całej tablicy.
Ważne jest to, że elementy umieszczone już na końcu tablicy nie biorą udziału w kolejnych przebudowach kopca. Są one traktowane jako gotowa, posortowana część.
Przykład sortowania stogowego
Weźmy niewielką tablicę:
[4, 10, 3, 5, 1]
Najpierw trzeba przekształcić ją w kopiec maksymalny. Po uporządkowaniu relacji pomiędzy elementami możemy otrzymać:
[10, 5, 3, 4, 1]
Największa wartość, czyli 10, znajduje się teraz na początku. Zamieniamy ją z ostatnim elementem:
[1, 5, 3, 4, 10]
Liczba 10 jest już na właściwym miejscu i nie będzie dalej ruszana. Pozostały fragment trzeba ponownie uporządkować jako kopiec:
[5, 4, 3, 1, 10]
Teraz największą wartością w niesortowanej części jest 5. Przenosimy ją na przedostatnią pozycję:
[1, 4, 3, 5, 10]
Po kolejnej naprawie kopca:
[4, 1, 3, 5, 10]
Następna zamiana daje:
[3, 1, 4, 5, 10]
Po wykonaniu wszystkich potrzebnych operacji otrzymujemy:
[1, 3, 4, 5, 10]
Na małej tablicy może się wydawać, że operacji jest sporo. Przewaga Heap Sort pojawia się przede wszystkim wtedy, gdy liczba elementów rośnie i zależy nam na przewidywalnej złożoności algorytmu.
Sortowanie stogowe w Pythonie
Implementacja Heap Sort w Pythonie składa się zazwyczaj z dwóch funkcji. Pierwsza odpowiada za poprawianie kopca, a druga przeprowadza właściwe sortowanie.
def heapify(tablica, n, i):
najwiekszy = i
lewy = 2 * i + 1
prawy = 2 * i + 2
if lewy < n and tablica[lewy] > tablica[najwiekszy]:
najwiekszy = lewy
if prawy < n and tablica[prawy] > tablica[najwiekszy]:
najwiekszy = prawy
if najwiekszy != i:
tablica[i], tablica[najwiekszy] = tablica[najwiekszy], tablica[i]
heapify(tablica, n, najwiekszy)
def heap_sort(tablica):
n = len(tablica)
for i in range(n // 2 - 1, -1, -1):
heapify(tablica, n, i)
for i in range(n - 1, 0, -1):
tablica[0], tablica[i] = tablica[i], tablica[0]
heapify(tablica, i, 0)
tablica = [4, 10, 3, 5, 1]
print("Przed sortowaniem:", tablica)
heap_sort(tablica)
print("Po sortowaniu:", tablica)
Wynik działania programu:
Przed sortowaniem: [4, 10, 3, 5, 1] Po sortowaniu: [1, 3, 4, 5, 10]
Jak działa kod Heap Sort?
Najwięcej uwagi wymaga funkcja heapify(). To ona sprawdza, czy element znajdujący się pod indeksem i jest odpowiednio ustawiony względem swoich dzieci.
Najpierw zakładamy, że największym elementem jest rodzic:
najwiekszy = i
Następnie wyliczane są indeksy jego dzieci:
lewy = 2 * i + 1 prawy = 2 * i + 2
Program sprawdza kolejno lewe i prawe dziecko. Jeżeli któreś z nich jest większe od rodzica, zapamiętywany jest jego indeks.
Gdy okaże się, że największy element nie znajduje się na pozycji rodzica, wykonywana jest zamiana:
tablica[i], tablica[najwiekszy] = tablica[najwiekszy], tablica[i]
Po zamianie funkcja wywołuje samą siebie dla niższego poziomu kopca. Jest to potrzebne, ponieważ przesunięcie jednego elementu może zaburzyć strukturę znajdującą się niżej.
Pierwsza pętla funkcji heap_sort() buduje kopiec maksymalny:
for i in range(n // 2 - 1, -1, -1):
heapify(tablica, n, i)
Druga pętla odpowiada już za przenoszenie największych elementów na koniec:
for i in range(n - 1, 0, -1):
tablica[0], tablica[i] = tablica[i], tablica[0]
heapify(tablica, i, 0)
Warto zwrócić uwagę na argument i przekazywany do funkcji heapify(). Oznacza on, że końcowa część tablicy nie jest już brana pod uwagę, ponieważ znajdują się tam wcześniej ustawione elementy.
Złożoność obliczeniowa Heap Sort
Jedną z mocniejszych stron sortowania stogowego jest jego przewidywalność. W przeciwieństwie do niektórych algorytmów Heap Sort nie wpada w bardzo niekorzystny przypadek O(n²) tylko dlatego, że dane zostały ułożone w określony sposób.
| Przypadek | Złożoność czasowa |
|---|---|
| Najlepszy przypadek | O(n log n) |
| Przeciętny przypadek | O(n log n) |
| Najgorszy przypadek | O(n log n) |
| Dodatkowa pamięć | O(1) dla klasycznej wersji iteracyjnej kopcowania |
Samo utworzenie kopca można wykonać w czasie O(n). Później dla każdego elementu wykonywane są operacje związane z przywracaniem kopca, które wymagają maksymalnie O(log n) kroków. Stąd dla całego sortowania otrzymujemy O(n log n).
Pokazana wyżej wersja funkcji heapify() korzysta z rekurencji, dlatego w Pythonie stos wywołań zużywa niewielką dodatkową ilość pamięci. Klasyczny Heap Sort można jednak napisać również bez rekurencji.
Zalety i wady sortowania stogowego
Heap Sort ma kilka właściwości, które sprawiają, że nadal jest ważnym algorytmem omawianym przy nauce struktur danych i sortowania.
Zalety Heap Sort
- złożoność O(n log n) także w najgorszym przypadku,
- nie wymaga tworzenia drugiej tablicy o rozmiarze zależnym od liczby elementów,
- dobrze pokazuje praktyczne wykorzystanie struktury kopca,
- czas działania jest bardziej przewidywalny niż w przypadku klasycznego Quick Sort w niekorzystnym układzie danych,
- może sortować tablicę bezpośrednio w jej własnej pamięci.
Wady Heap Sort
- jest trudniejszy do zrozumienia niż sortowanie bąbelkowe czy przez wstawianie,
- nie jest algorytmem stabilnym,
- w praktycznych zastosowaniach może mieć gorszą lokalność pamięci niż niektóre inne algorytmy,
- jego implementacja jest mniej intuicyjna dla początkujących.
Brak stabilności oznacza, że dwa elementy o tej samej wartości mogą po sortowaniu zmienić swoją wzajemną kolejność. Dla zwykłej tablicy liczb zazwyczaj nie ma to znaczenia, ale może być istotne podczas sortowania bardziej złożonych danych.
Heap Sort a inne algorytmy sortowania
Sortowanie stogowe dobrze wypada pod względem teoretycznej złożoności, ale nie oznacza to, że zawsze będzie najlepszym sposobem sortowania danych.
| Algorytm | Typowa złożoność | Najgorszy przypadek | Stabilny |
|---|---|---|---|
| Heap Sort | O(n log n) | O(n log n) | Nie |
| Insertion Sort | O(n²) | O(n²) | Tak |
| Merge Sort | O(n log n) | O(n log n) | Tak |
| Quick Sort | O(n log n) | O(n²) | Zwykle nie |
Sortowanie przez wstawianie jest prostsze i może dobrze sprawdzać się dla niewielkich albo prawie uporządkowanych tablic. Heap Sort jest bardziej złożony, ale utrzymuje O(n log n) niezależnie od początkowego ułożenia danych.
Merge Sort również gwarantuje O(n log n), lecz jego klasyczna wersja potrzebuje dodatkowej pamięci na tablice pomocnicze. Quick Sort natomiast jest bardzo popularny i zwykle szybki, ale jego najgorszy przypadek ma złożoność O(n²).
W praktyce języki programowania korzystają z bardziej dopracowanych lub hybrydowych rozwiązań. Dlatego Heap Sort warto znać przede wszystkim jako algorytm, który dobrze łączy temat sortowania z nauką drzew i kopców.
Komentarze