Algorytmy i Struktury Danych

[ Pobierz całość w formacie PDF ]
Algorytmy i Struktury Danych
Autor: Paweł Szymankiewicz
 
 
Bubble sort / Sortowanie bąbelkowe
Złożoność czasowa:
O(n
2
)
; 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 DZIAŁ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(n
2
)
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 DZIAŁANIA:
1. Utwórz zbiór elementów posortowanych i przenieś do niego dowolny element ze
zbioru nieposortowanego.
2. Weź 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ÓWNAŃ 
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(n
2
)
Sortowanie przez wybieranie
polega na wyszukaniu elementu mającego się znaleźć na
zadanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest
wykonywana dla wszystkich indeksów zadanej tablicy.
SCHEMAT DZIAŁ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 
[0,
1
,6,8,4,3,2,9
] 
1 (element znajduje się na właściwej pozycji) 
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. Łą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 DZIAŁ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 wskaźniki na swojego prawego i lewego syna. 
 
5
 
 
[ Pobierz całość w formacie PDF ]