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.

Opis algorytmu

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.

Tworzenie kopca

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).

Sortowanie

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).

Porównanie z innymi algorytmami sortowania

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(n²), 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

NEXT

' Gotowe

Input Box ("Koniec naciśnij klawisz Enter...")

END Sub.

Góra dokumentu

Sortowanie bąbelkowe

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(n²) 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:

58

2

33

3

17

1

20

2

58

33

3

17

1

20

2

33

58

3

17

1

20

2

33

3

58

17

1

20

2

33

3

17

58

1

20

2

33

3

17

1

58

20

2

33

3

17

1

20

58

Przypatrz się teraz liczbie 58. Widzisz jej drogę ? Wędruje po kolei na właściwe miejsce, na górę. W następnym przebiegu lecieć do góry będzie liczba 33 itd. Stąd właśnie nazwa algorymu. Tak jak bąbelki w wodzie wypływają do góry tak tutaj największe liczby "wypływają" na koniec tablicy.

Przy okazji można zauważyć sporą wadę tego algorytmu. Tzw. puste przebiegi. Po pewnym czasie początkowe indeksy tablicy są już uporządkowane, a nasz algorytm dalej za każdym razem "jeździ" po nich i porównuje liczby. Można go poprawić, zapamiętując za każdym razem indeks tablicy od którego liczby są już uporządkowane, ale nie zmieni to klasy algorytmu, nadal będzie to algorytm klasy O(n²).

Schemat blokowy sortowania bąbelkowego

Przykład sortowania bąbelkowego w Visual Basic

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

Góra dokumentu

Sortowanie przez scalanie

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 (ang. divide and conquer). Ideą działania tego typu algorytmów jest podział problemu na mniejsze części, których rozwiązanie jest już łatwiejsze. Odkrycie algorytmu przypisuje się Johnowi von Neumannowi.

Tutaj można wyróżnić trzy podstawowe kroki:

1. Podziel zestaw danych na dwie, równe części;

2. Zastosuj sortowanie przez scalanie dla każdej z nich odzielnie, chyba że pozostał już tylko jeden element;

3. Połącz posortowane podciągi w jeden.

Procedura scalania dwóch ciągów A[1..n] i B[1..m] do ciągu C[1..m+n]:

1. Uwórz wskaźniki na początki ciągów A i B -> i=0, j=0

2. Jeżeli A[i] < = B[j] wstaw A[i] do C i zwiększ i o jeden, w przeciwnym przypadku wstaw B[j] do C i zwiększ j o jeden

3. Powtarzaj krok 2 aż wszystkie wyrazy A i B trafią do C

A więc scalenie dwóch wymaga O(n+m) operacji porównań elementów i wstawienia ich do tablicy wynikowej.

Złożoność czasowa algorytmu sortowania przez scalanie

Bez straty ogólności załóżmy, że długość ciągu, który mamy posortować jest potęgą 2ki (patrz Złożoność obliczeniowa)

Poniższy obrazek przedstawia drzewo rekursji wywołania algorytmu mergesort, wartości po prawej oznaczają czas wykonania każdego poziomu.

Mamy więc drzewo o głębokości log₂ n, na każdym poziomie dokonujemy scalenia
o łącznym koszcie nxc, gdzie c jest stałą zależną od komputera. A więc intuicyjnie, tzn. nieformalnie możemy dowieść, że złożoność algorytmu mergesort to log₂ n x n

Formalnie złożoność czasową sortowania przez scalanie możemy przedstawić następująco:

T(1) = O(1)

Ciągi jednoelementowe możemy posortować w czasie stałym, czas sortowania ciągu
n elementowego to scalenie dwóch ciągów
elementowych ( czyli 0(n)) , plus czas potrzebny na posortowanie dwóch, o połowę mniejszych ciągów.

Mamy:

gdzie n = 2^k

Po rozwinięciu nawiasów otrzymamy:

T(n) = 2nlogn

A więc asymptotyczny czas sortowania przez scalanie wynosi O(n log n) (zobacz: notacja dużego O).

Dowód poprawności algorytmu sortowania przez scalanie

Dowód przez indukcję względem długości n tablicy elementów do posortowania.

1) n=2

Algorytm podzieli dane wejściowe na dwie części, po czym zastosuje dla nich scalanie do posortowanej tablicy

2) Zał.: dla ciągów długości k, k<n algorytm mergesort prawidłowo sortuje owe ciągi.

Dla ciągu długości n algorytm podzieli ten ciąg na 2 długości n/2. Na mocy założenia indukcyjnego ciągi te zostaną prawidłowo podzielone i scalone do dwóch, posortowanych ciągów długości n/2. Ciągi te zostaną natomiast scalone przez procedurę scalającą do 1go, posortowanego ciągu długości n.

Schemat blokowy sortowania przez scalanie.

Przykład sortowania przez scalanie w Visual Basic.

Sub sortowanie_babelkowe()

OPTION EXPLICIT

CONST N = 20 ' Liczebność zbioru.

DIM SHARED d(1 TO N) AS INTEGER

DIM SHARED p(1 TO N) AS INTEGER

DECLARE SUB MergeSort(BYVAL i_p AS INTEGER, BYVAL i_k AS INTEGER)

DIM i AS INTEGER

InputBox(„Sortowanie przez scalanie”)

' Najpierw wypełniamy tablicę d() liczbami pseudolosowymi

' a następnie wyświetlamy jej zawartość

RANDOMIZE TIMER

FOR i = 1 TO N: d(i) = INT(RND * 100): NEXT

PRINT "Przed sortowaniem:"

PRINT

FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT

PRINT

' Sortujemy

MergeSort 1, N

' Wyświetlamy wynik sortowania

InputBox("Po sortowaniu:")

FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT

InputBox("Nacisnij Enter...")

SLEEP

END

' Procedura sortująca

'--------------------

PUBLIC SUB MergeSort(BYVAL i_p AS INTEGER, BYVAL i_k AS INTEGER)

DIM i_s AS INTEGER, i1 AS INTEGER, i2 AS INTEGER, i AS INTEGER

i_s = INT((i_p + i_k + 1) / 2)

IF i_s - i_p > 1 THEN MergeSort i_p, i_s - 1

IF i_k - i_s > 0 THEN MergeSort i_s, i_k

i1 = i_p: i2 = i_s

FOR i = i_p TO i_k

IF (i1 = i_s) OR ((i2 <= i_k) AND (d(i1) > d(i2))) THEN

p(i) = d(i2): i2 = i2 + 1

ELSE

p(i) = d(i1): i1 = i1 + 1

END IF

NEXT

FOR i = i_p TO i_k: d(i) = p(i): NEXT

END SUB

Góra dokumentu

Sortowanie szybkie

Sortowanie szybkie (ang. quicksort) - jeden z popularnych algorytmów sortowania działających na zasadzie "dziel i zwyciężaj".

W teorii obliczeń dziel i zwyciężaj (ang. divide and conquer) jest ważną strategią konstruowania algorytmów i jedną z najefektywniejszych metod algorytmicznych
w informatyce. W strategii tej rekurencyjnie dzielimy problem na dwa lub więcej mniejszych podproblemów tego samego (lub podobnego) typu tak długo, aż stanie się on wystarczająco prosty do bezpośredniego rozwiązania. Z kolei rozwiązania otrzymane dla mniejszych podproblemów scalamy uzyskując rozwiązanie całego zadania.

Klasyczne przykłady algorytmów korzystających z tej metody, to m.in: mergesort, quicksort, wyszukiwanie binarne.

Zasada

Algorytm działa rekursywnie - wybieramy pewien element tablicy, tzw. element dzielący, po czym na początek tablicy przenosimy wszystkie elementy mniejsze od niego, na koniec wszystkie większe, a w powstałe między tymi obszarami puste miejsce trafia wybrany element. Potem sortujemy osobno początkową i końcową część tablicy. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa podtablica jest oczywiście posortowana.

Jeśli przez l oznaczymy indeks pierwszego, a przez r - ostatniego elementu sortowanego fragmentu tablicy, zaś przez i - indeks elementu, na którym tablica została podzielona, to procedurę sortowania można (w dużym uproszczeniu) przedstawić następującym, pascalo-podobnym zapisem:

PROCEDURE Quicksort(l, r)

BEGIN

IF l < r THEN { jeśli fragment dłuższy niż 1 element }

BEGIN

i = PodzielTablice(l, r); { podziel i zapamiętaj punkt podziału }

Quicksort(l, i-1); { posortuj lewą część }

Quicksort(i, r); { posortuj prawą część }

END

END

Algorytm sortowania szybkiego jest bardzo wydajny: jego średnia złożoność obliczeniowa jest rzędu O(n·log n) (zob. hasło Notacja dużego O). Jego szybkość i prostota implementacji powodują, że jest powszechnie używany; jego implementacje znajdują się również
w standardowych bibliotekach języków programowania - na przykład w bibliotece standardowej języka C, w implementacji klasy TList w Delphi, jako procedura standardowa
w PHP itp.

Złożoność

Algorytm ten dość dobrze działa w praktyce, ale ma bardzo złą pesymistyczną złożoność.

Przypadek optymistyczny

W przypadku optymistycznym, jeśli mamy szczęście za każdym razem wybrać medianę
z sortowanego fragmentu tablicy, to liczba porównań niezbędnych do uporządkowania
n-elementowej tablicy opisana jest rekurencyjnym wzorem

Dla dużych n:

co daje w rozwiązaniu liczbę porównań (a więc wskaźnik złożoności czasowej):

Równocześnie otrzymuje się minimalne zagnieżdżenie rekursji (czyli głębokość stosu, a co za tym idzie, złożoność pamięciową):

(Symbol logarytmu bez oznaczonej podstawy oznacza tu logarytm dwójkowy.)

Przypadek przeciętny

W przypadku przeciętnym, to jest dla równomiernego rozkładu prawdopodobieństwa wyboru elementu z tablicy:

złożoność jest zaledwie o 39% wyższa, niż w przypadku optymistycznym.

Przypadek pesymistyczny

W przypadku pesymistycznym, jeśli zawsze wybierzemy element najmniejszy (albo największy) w sortowanym fragmencie tablicy, to:

skąd wynika kwadratowa złożoność czasowa:

W tym przypadku otrzymuje się też olbrzymią, liniową złożoność pamięciową:

Schemat blokowy sortowania szybkiego.

Przykład sortowania szybkiego w Visual Basic.

DECLARE SUB Sortuj_szybko(lewy AS INTEGER, prawy AS INTEGER)

CONST N = 20 ' liczebność zbioru

DIM SHARED d(N) AS INTEGER

DIM i AS INTEGER

InpurBox("Przed sortowaniem:": PRINT)

' Wypełniamy tablicę liczbami pseudolosowymi i wyświetlamy je

RANDOMIZE

FOR i = 1 TO N

d(i) = INT(RND * 100): PRINT USING "####";d(i);

NEXT

PRINT

' Sortujemy

Sortuj_szybko(1,N)

' Wyświetlamy wynik sortowania

PRINT "Po sortowaniu:": PRINT

FOR i = 1 TO N: PRINT USING "####";d(i);: NEXT

PRINT

PRINT "Nacisnij Enter..."

SLEEP

END

' Procedura sortowania szybkiego

'-------------------------------

SUB Sortuj_szybko(lewy AS INTEGER, prawy AS INTEGER)

DIM AS INTEGER i, j, piwot

i = (lewy + prawy) \ 2

piwot = d(i): d(i) = d(prawy)

j = lewy

FOR i = lewy TO prawy - 1

IF d(i) < piwot THEN

SWAP d(i), d(j)

j += 1

END IF

NEXT

d(prawy) = d(j): d(j) = piwot

IF lewy < j - 1 THEN Sortuj_szybko(lewy, j - 1)

IF j + 1 < prawy THEN Sortuj_szybko(j + 1, prawy)

END SUB

Góra dokumentu

8

i ← 2

Start

i ≤ n

Koniec

Tak

Nie

j ← i

k ← j div a

x ← d[i]

k > 0

d[k] < x

d[j] ← d[k]

j ← k

k ← j div 2

d[k] ← x

i ← i + 1

Tak

Tak

Nie

Nie

Start

j:=n;

i:=1;

i<j

a[i]>a[i+1]

x:= a[i];

a[i]=a[i+1];

a[i+1]:= x

Tak

Nie

Tak

Tak

i:= i+1

Nie

j:=j-1

j>1

Stop

Nie

Koniec

Sortuj_szybko(j + 1, prawy)

Tak

j + 1 < prawy

Sortuj_szybko(lewy, j - 1)

Tak

lewy < j

d[prawy] ← d[j]

d[j] ← piwot

i ← i + 1

d[i] ↔ d[j]

j ← j + 1

Tak

d[i] < piwot

Tak

i < prawy

i ← lewy

piwot ← d[i]

d[i] ← d[prawy]

j ← lewy

i ←

Start

Start

i₁ ← i_p

i₂ ← i_s

i ← i_p

i ≤ i_k

Tak

i₁ = i₂

i₂ > i_k

d[i₂] ≤ d[i₂]

p[i] ← d[i₂]

i₂ ← i₂ + 1

p[i] ← d[i₁]

i₁ ← i₁ + 1

i ← i + 1

Tak

Tak

Tak

i ← i_p

i ≤ i_k

Tak

d[i] ← d[i₂]

i ← i + 1

Koniec

---