Spis treści
1. Sortowanie kopcem
2. Sortowanie bąbelkowe
3. Sortowanie przez scalanie
4. Sortowanie szybkie
Sortowanie kopcem (ang. heapsort) - zwane też inaczej sortowaniem przez kopcowanie. Algorytm ten jest jedną z ciekawszych metod sortowania z racji faktu, iż jest on szybki oraz nie pochłania zbyt wiele zasobów pamięci. Jego złożoność czasowa to O(n log n), a pamięciowa O(1). Algorytm ten jest nieco wolniejszy od sortowania szybkiego, lecz ma lepszą pesymistyczną złożoność czasową. Sortowanie przez kopcowanie jest niestabilne, co może być czasami uznawane za wadę. Do jego wad można też zaliczyć fakt, iż jest on stosunkowo skomplikowany w implementacji.
Podstawą algorytmu jest użycie kolejki priorytetowej zaimplementowanej w postaci binarnego kopca zupełnego. Szczegóły implementacji kopca wyjaśnione są w artykule kopiec. Zaletą kopca jest to, że oprócz stałego czasu dostępu do elementu maksymalnego (lub minimalnego) oferuje on logarytmiczny czas wstawiania i usuwania elementów. Ponadto kopiec można łatwo implementować w postaci tablicy.
Algorytm sortowanie przez kopcowanie składa się z dwóch faz. W pierwszej sortowane elementy reorganizowane są w celu utworzenia kopca. W drugiej zaś dokonywane jest właściwe sortowanie.
Podstawową zaletą algorytmu jest to, że do stworzenia kopca wykorzystać można tę samą tablicę, w której początkowo znajdują się nieposortowane elementy. Dzięki temu uzyskuje się stałą złożoność pamięciową.
Początkowo do kopca należy tylko pierwszy element w tablicy. Następnie kopiec rozszerzany jest o drugą, trzecią i kolejne pozycje tablicy, przy czym przy każdym rozszerzeniu, nowy element jest przemieszczany w górę kopca, tak aby spełnione były relacje pomiędzy węzłami. Schematycznie wygląd sortowanej tablicy można przedstawić w następujący sposób:
-----------------------------------------------------------
| Kopiec | Reszta nieposortowanych elementów |
a kopiec rozrasta się, aż do wyczerpania nieposortowanej części tablicy.
Dzięki logarytmicznej złożoności pojedynczych operacji wstawiania (rozszerzania kopca), całkowita złożoność tego etapu to O(nlog n).
Można też ten krok wykonać szybciej - w czasie O(n). W tym celu należy budować kopiec w następujący sposób:
| Reszta nieposortowanych elementów | Małe kopce |
Aby osiągnąć taką strukturę, wystarczy pierwsze n div 2 elementów tablicy (zakładając, że kopiec implementujemy w tablicy) przesunąć w dół kopca procedurą shift-down:
shift-down (T[1..n], i)
k ← i
repeat
j ← k
if 2 * j <= n and T[2 * j] > T[k]
k ← 2 * j
if 2 * j + 1 <= n and T[2 * j + 1] > T[k]
k ← 2 * j + 1
until j = k
Zatem procedura budująca kopiec wyglądałaby następująco:
build-heap (T[1..n])
for i ← n div 2 downto 1
shift-down (T, i)
Procedura build-heap buduje kopiec w czasie O(n).
Po utworzeniu kopca następuje właściwe sortowanie. Polega ono na usunięciu wierzchołka kopca, zwierającego element maksymalny (minimalny), a następnie wstawieniu w jego miejsce elementu z końca kopca i odtworzenie porządku kopcowego. W zwolnione w ten sposób miejsce, zaraz za końcem zmniejszonego kopca wstawia się usunięty element maksymalny. Operacje te powtarza się aż do wyczerpania elementów w kopcu. Wygląd tablicy można tu schematycznie przedstawić następująco:
| Kopiec elementów do posortowania | Posortowana tablica |
Tym razem kopiec kurczy się, a tablica przyrasta (od elementu ostatniego do pierwszego).
Także, tu złożoność usuwania elementu połączonego z odtwarzaniem porządku kopcowego, ma złożoność logarytmiczną, a zatem złożoność tej fazy to O(nlog n).
Algorytm sortowania przez kopcowanie jest na ogół nieco wolniejszy niż Sortowanie Szybkie. Jego przewagą natomiast jest lepsza złożność pesymistyczna wynosząca O(n log n), podzas gdy dla quicksort jest to O(n2), co jest nie do przyjęcia, dla dużych zbiorów danych. Także złożność pamięciowa O(1) jest lepsza niż Ω(log n) alorytmu quicksort.
Heapsort jest nieco szybszy od algorytmu mergesort, mającego taką samą asympotyczną złożoność czasową. Mergesort wymaga jednak Ω(n) dodatkowej pamięci. Zaletą mergesort jest prostsza definicja i lepsze zachowanie w przypadkach, gdy dane do sortowania pobierane są z wolnej pamięci masowej; jest też łatwiejszy do zrównoleglenia.
Schemat blokowy sortowania kopcem:
Sortowanie kopcem przykład w Visual Basic.
Sub sortowanie_kopcem()
CONST N = 31 ' liczba elementów
DIM d(N) AS INTEGER
DIM i AS INTEGER, j AS INTEGER, k AS INTEGER, x AS INTEGER
RANDOMIZE
InputBox("Tworzenie kopca")
' Inicjujemy zbiór d[] liczbami pseudolosowymi od 0 do 9
FOR i = 1 TO N: d(i) = INT(RND * 10): NEXT
' Budujemy kopiec
FOR i = 2 TO N
j = i: k = j \ 2
x = d(i)
WHILE (k > 0) AND (d(k) < x)
d(j) = d(k)
j = k: k = j / 2
WEND
d(j) = x
NEXT
' Prezentujemy wyniki
x = (N + 1) \ 2: k = 2
FOR i = 1 TO N
FOR j = 1 TO x - 1: PRINT " ";: NEXT
PRINT USING "#";d(i);
FOR j = 1 TO x: PRINT " ";: NEXT
IF i + 1 = k THEN
k = k + k: x = x \ 2:
PRINT
END IF
' Gotowe
Input Box ("Koniec naciśnij klawisz Enter...")
END Sub.
Góra dokumentu
Sortowanie bąbelkowe to jeden z najprostszych algorytmów sortowania. Zaraz wyjaśni się skąd ta dziwna nazwa :). Nie jest to niestety algorytm zbyt szybki. Jego złożoność to O(n2) czyli jeżeli dostanie 20 liczb do posortowania, to w najgorszym przypadku będzie musiał wykonać 400 operacji.
No a teraz najważniejsze - jak to działa. Otóż bardzo prosto:
· Porównujemy po kolei elementy ze sobą sąsiadujące czyli 1 z 2, 2 z 3, 3 z 4, 4 z 5, 5 z 6 itd.
· Jeżeli element po lewej jest większy od elementu po prawej to zamieniamy je ze sobą (jeżeli nie, to nic nie robimy)
· Całość powtarzamy tyle razy, ile jest elementów, lub jeżeli po porównaniu wszystkich elementów nie zamieniliśmy żadnych miejscami
Myślę że problemów ze zrozumieniem nie miałeś, no ale prześledźmy działanie algorytmu na przykładzie. Załóżmy że mamy taką oto 7 elementową tablicę:
58
2
33
3
17
1
20
No i teraz wykonywanie kroków 1 i 2. Elementy porównywane są podkreślone:
Schemat blokowy sortowania bąbelkowego
Option Base 1
Const N = 10
Const MAXVALUE = 20
Dim a(N) As Integer
Sub SortBubble()
Dim i As Integer, j As Integer, v As Integer
For i = 1 To N
For j = 1 To N - i
If a(j) > a(j + 1) Then
v = a(j)
a(j) = a(j + 1)
a(j + 1) = v
End If
Next j
Next i
End Sub
W informatyce sortowanie przez scalanie (ang. merge sort), to rekurencyjny algorytm sortowania danych.
Algorytm ten jest dobrym przykładem algorytmów typu Dziel i zwyciężaj ...
Rzulu5