Algorytmy i Struktury Danych
Autor: Paweł Szymankiewicz
Bubble sort / Sortowanie bąbelkowe
Złożoność czasowa: O(n2); pamięciowa: O(1)
Sortowanie bąbelkowe polega na porównywaniu dwóch kolejnych elementów i zamianie ich
kolejności, jeżeli zaburza ona założony porządek. Sortowanie kończy się, gdy podczas
kolejnego przejścia nie dokonano żadnej zmiany.
SCHEMAT DZIAA
ANIA:
{ 4, 2, 5, 1, 7 } >>> { 2, 4, 5, 1, 7 } >>> { 2, 4, 5, 1, 7 } >>> { 2, 4, 1, 5, 7 } >>> { 2, 4, 1, 5, 7 } >>>
>>> { 2, 4, 1, 5, 7 } >>> { 2, 1, 4, 5, 7 } >>> { 2, 1, 4, 5, 7 } >>> { 1, 2, 4, 5, 7 } >>> { 1, 2, 4, 5, 7 }
Insert sort / Sortowanie przez wstawianie
Złożoność obliczeniowa: O(n2)
Sortowanie przez wstawianie, jego zasada działania odzwierciedla sposób w jaki ludzie
układają karty  kolejne elementy wejściowe są ustawiane na odpowiednie miejsca
docelowe. Jest efektywny dla niewielkiej ilości elementów. Główne zalety insert sort a to:
" Wydajny dla danych wstępnie posortowanych
" Wydajny dla zbiorów o niewielkiej liczebności
" Stabilny
SCHEMAT DZIAA
ANIA:
1. Utwórz zbiór elementów posortowanych i przenieś do niego dowolny element ze
zbioru nieposortowanego.
2. Wez
dowolny element ze zbioru nieposortowanego.
3. Wyciągnięty element, porównuj z kolejnymi elementami zbioru posortowanego,
dopóki nie napotkasz elementu równego lub elementu większego (jeśli chcemy
otrzymać ciąg niemalejący) lub nie znajdziemy się na początku/końcu zbioru
uporządkowanego.
4. Wyciągnięty element wstaw w miejsce gdzie skończyłeś porównywać.
5. Jeżeli zbiór elementów nieposortowanych jest niepusty, wróć do punktu 2.
1
" Insert sort (tablica) - SCHEMAT
CI
G ZNAKÓW ILOŚĆ PORÓWNAC
ILOŚĆ ZAMIAN
|ELDCGBHA
E|LDCGBHA
EL|DCGBHA 1 0
DEL|CGBHA 2 2
CDEL|GBHA 3 3
CDEGL|BHA 2 1
BCDEGL|HA 5 5
BCDEGHL|A 2 1
ABCDEGHL| 7 7
= 22 = 19
" Insert sort (lista)  SCHEMAT
Ciąg znaków: 5, 8, 4, 3, 6,
1. 5 // dodajemy do listy 5
2. 8, 5 // dodajemy do listy 8 i sprawdzamy z 5. 8 > 5 &
3. 5, 8 // & więc zamieniamy je miejscami
4. 4, 5, 8 // dodajemy 4 do listy i sprawdzamy z 5. Jest OK.
5. 3, 4, 5, 8 // dodajemy 3 do listy i sprawdzamy z 4. Jest OK.
6. 6, 3, 4, 5, 8 // dodajemy 6 do listy i sprawdzamy z 3. 6 > 3
7. 3, 4, 5, 6, 8 // sprawdzamy i zamieniamy aż do stanu OK.
2
Select sort / Sortowanie przez wybieranie
Złożoność: O(n2)
Sortowanie przez wybieranie polega na wyszukaniu elementu mającego się znalez
ć na
zadanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest
wykonywana dla wszystkich indeksów zadanej tablicy.
SCHEMAT DZIAA
ANIA:
1. Wyszukaj minimalną wartość tablicy od i+1 do końca tablicy.
2. Zamień wartość minimalną z wartością na pozycji i.
NUMER ITERACJI (i) TABLICA MINIMUM
0 [9,1,6,8,4,3,2,0] 0
1 (element znajduje się na właściwej pozycji)
1 [0,1,6,8,4,3,2,9]
2 [0,1,6,8,4,3,2,9] 2
& & &
Quicksort / Sortowanie szybkie
Średnia złożoność obliczeniowa: O(n*log n)
Algorytm sortowania szybkiego działa rekursywnie  wybieramy pewien element tablicy,
tzw. element osiowy, a następnie wszystkie elementy mniejsze od niego przenosimy na
początek tablicy, a większe na koniec. Następnie sortujemy pierwszą  połówkę i drugą
tablicy w ten sam sposób. Algorytm kończy swoje działanie, gdy zbiór do posortowania
składa się z jednego elementu.
3
Shell sort / Sortowanie metodą Shella
Metoda Shella polega na tym, że sortowany zbiór dzielimy na podzbiory, których elementy są odległe
od siebie o określoną odległość h. Każdy z tych podzbiorów, sortujemy wykorzystując algorytm
sortowania przez wstawianie. Następnie odstęp zmniejszamy. Powoduje to powstanie nowych
podzbiorów  będzie ich już mniej. Sortowanie powtarzamy do chwili, gdy odległość h osiągnie
wartość 1. Wtedy ponownie sortujemy ciąg znaków za pomocą Insert sort (Sortowanie przez
wstawianie).
Merge sort / Sortowanie przez scalanie
Złożoność czasowa: O(n log n)
Sortowanie przez scalanie to rekurencyjny algorytm sortowania danych, mający zastosowanie przy
danych dostępnych sekwencyjnie (po kolei, jeden element na raz), na przykład w postaci listy
jednokierunkowej (tj. A
ączonej jednostronnie) albo pliku sekwencyjnego.
Opisując działanie algorytmu w skrócie  problem, który został nam postawiony dzielimy na mniejsze
części, których rozwiązanie jest już łatwiejsze
SCHEMAT DZIAA
ANIA:
1. Podziel zestaw danych na dwie równe części.
2. Zastosuj sortowanie przez scalanie dla każdej z części (chyba, że pozostał już tylko jeden
element)
3. Połącz posortowane części w jedną.
Heapsort / Sortowanie przez kopcowanie
Złożoność czasowa: O(n log n)
Podstawą sortowania przez kopcowanie jest użycie kolejki priorytetowej zaimplementowanej
w postaci binarnego kopca zupełnego.
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
4
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.
Po utworzeniu kopca następuje właściwe sortowanie. Polega ono na usunięciu wierzchołka
kopca, zawierają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.
Drzewa binarne / Binary Tree
Drzewo binarne to informatyczna struktura danych, w której liczba synów każdego
wierzchołka nie jest większa niż dwa. Wyróżniamy wtedy lewego i prawego syna danego
wierzchołka.
Binarne drzewo poszukiwań / Binary Search Tree (BST)
Binarne drzewo poszukiwań to dynamiczna struktura będąca drzewem binarnym, w którym lewe
poddrzewo każdego węzła zawiera wyłącznie elementy o kluczach nie większych niż klucz węzła, a
poddrzewo prawe zawiera wyłącznie elementy nie mniejsze niż klucz węzła.
Węzły poza kluczem, zawierają także wskaz
niki na swojego prawego i lewego syna.
5
Wyszukiwanie w Binarnym drzewie poszukiwań
Jedną z podstawowych operacji, jakie możemy wykonać na drzewie BST, jest operacja
wyszukiwania.
Operację wyszukiwania rozpoczynamy ze wskaz
nikiem ustawionym na korzeń drzewa. W
polu metody przekazujemy wartość poszukiwanego klucza. Następnie przekazany klucz, jest
porównywany z każdym kluczem zawierającym się w napotkanym węz
le
" Jeżeli obie wartości są równe, zwracamy adres porównywanego węzła.
" Jeżeli wartość poszukiwanego klucza jest mniejsza niż wartość klucza w
napotkanym węz
le to dalsze poszukiwania są prowadzone tylko w lewym
poddrzewie.
" Jeżeli wartość poszukiwanego klucza jest większa niż wartość klucza w napotkanym
węz
le to dalsze poszukiwania są prowadzone tylko w prawym poddrzewie.
public Node search (int key)
{
Node node = root;
while (node != null)
{
int result = key - node.getKey();
if (result == 0)
{
return node;
}
else if (result < 0)
{
node = node.getLeftChild();
}
else
{
node = node.getRightChild();
}
}
return null;
}
6
Wstawianie w Binarnym drzewie poszukiwań
public void insert (Node z)
{ }
Node y = null;
Node x = root; z.setParent(y);
while (x != null) if (y == null)
{ {
y = x; root = z;
}
if (z.getKey() < x.getKey()) else if (z.getKey() < y.getKey())
{ {
x = x.getLeftChild(); y.setLeftChild(z);
} }
else
else {
{ y.setRightChild(z);
x = x.getRightChild(); }
} }
Usuwanie w Binarnym drzewie poszukiwań
Operacja usuwania w Binarnym drzewie poszukiwań jest dużo bardziej skomplikowana niż
jego wstawienie. Należy rozpatrzyć 3 przypadki.
" W przypadku, gdy usuwany węzeł nie ma synów (jest liściem), jego usunięcie
przebiega bez reorganizacji drzewa. Wskaz
nik do węzła w jego ojcu, jest po prostu
zamieniany na wskaz
nik do węzła pustego.
" W przypadku, gdy usuwany węzeł ma jednego syna, to dany węzeł usuwamy, a w
jego miejsce wstawiamy jego syna.
" W przypadku, gdy usuwany węzeł ma dwóch synów, to po jego usunięciu, w jego
miejsce wstawiamy węzeł, który jest jego następnikiem (nie ma lewego syna).
7
B-Drzewo
B-Drzewo to inaczej drzewo wyważone, drzewo zrównoważone. Jest to drzewo, którego
wszystkie liście są w tej samej odległości od korzenia. Ta właściwość powoduje, że czas
przeszukiwania B-Drzewa jest stały dla każdej zapamiętanej w nim informacji. B-Drzewa
znajdują zastosowanie przy przeszukiwaniu dysków i innych pamięci zewnętrznych.
SCHEMAT B-DRZEWA
Ciąg znaków: D, B, K, R, T, A, C, E, F, G, L, S, W
D
B K R T
A C E F G L S W
1. Wstaw J.
" Rozbij KRT
D R
B K T
A C E F G L S W
" Podziel EFG i wstaw J.
D R
B K F T
A C G J E S W
L
8
2. Usuń L.
" Pożycz J od G,J i usuń L.
D R
B F J T
A C E G K L S W
3. Usuń W
" Pożycz J od FJ. Scal RT.
D J
B F R T
A C E G K S W
" Scal STW. Usuń W.
D J
B F R
A C E G K S T W
9
4. Usuń C.
" Scal BDF.
J
B D F R
A C E G K S T
" Scal ABC, usuń C.
J
D F R
A B C E G K S T
5. Usuń J.
G
B R
A E F K S T
10
Drzewo AVL
Drzewo AVL zwane również drzewem dopuszczalnym to zrównoważone drzewo poszukiwań
(BST), w którym wysokość lewego i prawego poddrzewa różni się co najwyżej o 1.
Wierzchołki drzewa AVL są uporządkowane tak samo jak w przypadku drzewa BST.
Zrównoważenie drzewa otrzymujemy, dzięki przypisaniu każdemu węzłowi współczynnika
wyważenia, który jest równy różnicy wysokości lewego i prawego poddrzewa.
Współczynnik ten może wynosić odpowiednio: -1, 0 lub 1. Wstawiając lub usuwając węzeł
w drzewie AVL modyfikujemy także wspomniany współczynnik wyważenia i w momencie,
gdy osiągnie on niedozwoloną wartość, wykonywana jest operacja rotacji węzłów, która
przywraca wyważenie.
Wstawianie elementów do Drzewa AVL
Wstawianie nowego elementu do drzewa AVL może odbywać się na zasadach poznanych
przy okazji drzewa BST. Następnie odtwarzamy te same kroki w kierunku korzenia,
aktualizując współczynnik wyważenia.
Zmiana współczynnika wyważenia na 0 oznacza, że wysokość drzewa nie została zmieniona
 w tym momencie operację wstawiania uznajemy za zakończoną.
Zmiana współczynnika na 1 lub -1 oznacza, że poddrzewo, którego korzeniem jest
rozważany wierzchołek zachowuje własności drzewa AVL jednak jego wysokość uległa
zwiększeniu.
Natomiast jeżeli współczynnik wyważenia przyjmuje wartość 2 lub -2, oznacza to, że
przetwarzane drzewo straciło własność AVL. Aby ją przywrócić należy wykonać rotację. W
najgorszym wypadku potrzebne będą dwie rotacje.
Usuwanie elementów z Drzewa AVL
Jeżeli usuwany element jest liściem, jest po prostu usuwany z drzewa. W przeciwnym
przypadku, musi zostać zastąpiony największym elementem z jego lewego poddrzewa,
lub najmniejszym z prawego. Wyszukany największy/najmniejszy element ma co najwyżej
jedno dziecko, które zostaje teraz dzieckiem rodzica wyszukanego elementu. Po usunięciu,
odtwarzana jest ścieżka od rodzica wyszukanego elementu do korzenia, a współczynniki
wyważenia są aktualizowane.
11
Odtwarzanie może zostać zatrzymane, jeżeli współczynnik wyważenia zostaje zmieniony na
-1 lub 1, oznacza to bowiem, że wysokość poddrzewa zostaje nie zmieniona.
Zmiana współczynnika wyważenia na 0 oznacza zmniejszenie wysokości poddrzewa przez
co aktualizowanie współczynników musi być kontynuowane.
Jeżeli współczynnik przyjmie wartość -2 lub 2, to wykonywana jest rotacja w celu
przywrócenia wyważenia. W przeciwieństwie do operacji wstawiania, rotacji może być
więcej niż dwie.
Wyszukiwanie elementów w Drzewie AVL
Wyszukiwanie elementów w Drzewie AVL przebiega tak samo jak w BST.
Drzewo czerwono-czarne
Drzewo czerwono-czarne jest to rodzaj samoorganizującego się binarnego drzewa
poszukiwań. Ich implementacja jest bardzo skomplikowana, jednak złożoność obliczeniowa
bardzo mała.
Każdy węzeł w drzewie czerwono-czarnym ma dodatkowy atrybut  kolor. Ponadto, należy
spełniać następujące wymagania:
1. Każdy węzeł jest czerwony lub czarny.
2. Korzeń jest zawsze czarny.
3. Każdy liść jest czarny. NIL można traktować jako liść.
4. Jeżeli węzeł jest czerwony, to jego synowie muszą być czarni.
5. Każda ścieżka z ustalonego węzła do liścia, liczy tyle samo czarnych węzłów.
Dzięki temu, mamy gwarancję, że najdłuższa ścieżka od korzenia do liścia, będzie co
najwyżej dwukrotnie dłuższa, niż najkrótsza. Wynika to z następujących własności.
12
1. Zgodnie z własnością 4, żadna ścieżka nie zawiera dwóch czerwonych węzłów pod
rząd, jednak może zawierać czarne. Stąd najkrótsza ścieżka do węzła X zawiera
wyłącznie n czarnych węzłów.
2. Zgodnie z własnością 5, druga ścieżka wychodząca z węzła X musi zawierać także n
czarnych węzłów. Jedynym sposobem aby miała ona inną łączną długość jest
umieszczenie pomiędzy każdą parą węzłów czarnych węzła czerwonego.
3. Zgodnie z własnością 3, liść kończący obie ścieżki, musi być czarny. Jeżeli węzeł X
jest czarny, wtedy w ścieżce możemy rozmieścić co najwyżej n-1 węzłów
czerwonych, w przeciwnym przypadku będziemy mieli n czerwonych węzłów
(wliczając X).
Zatem łączna długość drugiej ścieżki może wynieść co najwyżej 2n, gdzie n jest długością
pierwszej ścieżki zbudowanej wyłącznie z węzłów czarnych.
Można udowodnić, że dla n węzłów głębokość drzewa czerwono-czarnego h wyniesie
najwyżej 2 log (n+1), przez co elementarne operacje będą wykonywać się w czasie O(log n).
Operacja rotacji
Rotacja w lewo powoduje spłynięcie danego
węzła na lewo w dół i wysunięcie do góry prawego
syna.
Rotacja w prawo zachodzi w drugą stronę. Węzeł
spływa na prawo, a w górę wyciągamy lego
lewego syna
Wstawianie elementów
1. Umieszczenie elementu za pomocą standardowego algorytmu dla binarnych drzew
poszukiwań.
2. Pokolorowanie nowego węzła na czerwono.
3. Przywrócenie własności drzew czerwono-czarnych.
Przywracając własności drzew czerwono-czarnych, rozpatrujemy 6 przypadków. Można
jednak sprawdzić tylko 3 z nich, ponieważ druga trójka jest ich symetrycznym odbiciem.
1. Brat ojca (stryj) węzła z jest czerwony.
2. Stryj węzła z jest czarny i z jest prawym synem.
3. Stryj węzła z jest czarny i z jest lewym synem.
Rozwiązując przypadek pierwszy, kolorujemy zarówno ojca jak i jego brata na czarno, a
następnie przesuwamy z na ich ojca, którego kolorujemy na czerwono.
Rozwiązując przypadek drugi, ustawiamy z na ojca dotychczasowego z i wykonujemy jego
rotację w lewo.
Rozwiązując przypadek trzeci, przekolorowujemy ojca z na czarno, jego ojca na czerwono, a
następnie wykonujemy rotację w prawo na ojcu ojca.
13
B E
A C G
D F
Przeszukiwanie w szerz / BFS
Algorytm zaczyna od korzenia i następnie przeszukuje połączone z nim węzły. W kolejnym
kroku odwiedza węzły połączone z tymi węzłami itp.
BFS (A): wykorzystujemy kolejkę FIFO i listę sąsiedztwa
A  B, C, D
B  C, E
C  G
D  C, F
E  G
F  G
Przeszukiwanie w głąb / DFS
Przeszukiwanie rozpoczynamy w korzeniu, poruszając się w dół grafu/drzewa do samego
końca gałęzi, po czym wraca o jeden poziom i próbuje kolejne gałęzie.
A B C G
ODWIEDZONY: S
SIEDZTWO:
A B, C, D
B C, E
D E
C G
D C, F
E G
F G
F
14
2
B E
10 2 2 2
4 1
A C G
3
1
5 1
D F
1
Algorytm Kruskala
Tworzy z grafu drzewo, którego waga jest najmniejsza z możliwych.
" CF  1
" CG  1
B E
" DF  1
" FG  1
" BC  2
" BE  2
C G
" EC  2
" EG  2
" DC  3
" BD  4
D F
" AD  5
A
" AB  10
Algorytm Prima
Algorytm Prima wykorzystuje kolejkę priorytetową. Budowę minimalnego drzewa
rozpinającego zaczynamy od dowolnego wierzchołka, np. pierwszego. Dodajemy
wierzchołem do drzewa, a wszystkie krawędzie od niego odchodzące umieszczamy w
posortowanej wg wag liście.
Następnie zdejmujemy z listy pierwszą krawędz
(o najmniejszej wadze), sprawdzamy, czy
drugi wierzchołek danej krawędzi należy już do drzewa, jeżeli tak  pomijamy go i pobieramy
z listy kolejną krawędz
. W przeciwnym wypadku dodajemy wierzchołek do drzewa. Kiedy
dodamy nowy wierzchołek, do listy dodajemy powiązane z nim wierzchołki, uporządkowane
wg priorytetu/wagi.
15
Algorytm Dijkstry
Algorytm Dijkstry znajduje w grafie wszystkie najkrótsze ścieżki pomiędzy wybranym
wierzchołkiem a wszystkimi pozostałymi, przy okazji wyliczając również koszt przejścia
każdej z tych ścieżek.
Metody drukowania
PreOrder:
8 3 1 6 4 7 10 14 13
InOrder:
1 3 4 6 7 8 10 13 14
PostOrder:
1 4 7 6 3 13 14 10 8
16