Algorytmy sortowania
i przeszukiwania
Algorytmy sortowania
i przeszukiwania
Spis treści
1.
Sortowanie przez wstawianie - InsertSort
2.
Sortowanie przez wybór – SelectionSort
3.
Algorytm sortowania bąbelkowego
4.
Rekurencja
5.
Szybkie sortowanie - quicksort
Sortowanie przez wstawianie -
InsertSort
3
4
7
6
8
1
Karty posortowane
Karty do posortowania
Metoda sortowania przez wstawianie używana jest najczęściej
przez
osoby grające w karty.
Polega ona na założeniu, że w danym momencie w ręku trzymamy
jednocześnie karty posortowane i nieposortowane.
W celu realizacji zadania porządkowania należy pobrać ze sterty
kart do posortowania kartę i wstawienia jej na odpowiednie
miejsce w obszarze
kart posortowanych.
Sortowanie przez wstawianie -
InsertSort
Dane:
n - liczba elementów w sortowanym zbiorze, d[ ] – zbiór,
który będzie sortowany.
Wynik:
Uporządkowany zbiór d[ ]
Algorytm: porządkowanie przez wstawianie– InsertSort
Krok 1.
Dla i = 1, 2, ..., n – 1 wykonaj kroki 2 … 4, a następnie
zakończ algorytm
Krok 2.
x ← d[j]; i ← j + 1
Krok 3.
Dopóki ( i ≤ n ) ∧ ( x > d[i] ): wykonuj d[i - 1] ← d[i];
i ← i + 1
Krok 4
d[i - 1] ← x
Sortowanie przez wstawianie -
InsertSort
for(j = n - 2; j >= 0; j--)
{
x = d[j];
i = j + 1;
while((i < n) && (x >
d[i]))
{
d[i - 1] = d[i];
i++;
}
d[i - 1] = x;
}
Sortowanie przez wstawianie -
InsertSort
Wnioski:
- algorytm ten jest bardzo kosztownym algorytmem
(klasa złożoności obliczeniowej – O(N
2
)
- nie nadaje się do porządkowania dużych zbiorów
- postać algorytmu przejrzysta
- algorytm krótki
Sortowanie przez wybór - SelectionSort
Metoda porządkowania przez wybór polega na porządkowaniu
zbioru
w sposób rosnący tzn. element najmniejszy powinien znaleźć się
na pierwszej pozycji. Metoda ta polega na znalezieniu w zbiorze
elementu najmniejszego i wymienieniu go z elementem na
czytanej pozycji zbioru aż do całkowitego jego uporządkowania.
Zbiór nieuporządkowany
4
7
2
9
3
4
7
2
9
3
2
7
4
9
3
2
7
4
9
3
2
3
4
9
7
2
3
4
9
7
2
3
4
9
7
2
3
4
9
7
2
3
4
7
9
Etapy porządkowania
Sortowanie przez wybór - SelectionSort
Dane:
n - liczba elementów zbioru,
d[ ] – zbiór sortowany. Elementy zbioru mają indeksy od
1 do n.
Wynik:
Uporządkowany zbiór d[ ]
Algorytm: porządkowanie przez wybór – Selection Sort
Idea:
najmniejszy wśród nieuporządkowanych daj na początek
Krok 1.
Dla j = 1, 2, ..., n - 1: wykonuj Krok 1 ...Krok 4, a
następnie zakończ algorytm
Krok 2.
p
min
← j
Krok 3.
Dla i = j + 1, j + 2, ..., n: jeśli d[i] < d[p
min
], to p
min
← i
Krok 4.
d[j] ↔ d[p
min
]
Sortowanie przez wybór - SelectionSort
for(j = 0; j < N - 1; j++)
{
pmin = j;
for(i = j + 1; i < N; i++)
{
if(d[i] < d[pmin]) pmin
= i;
}
swap(d[pmin], d[j]);
}
Sortowanie przez wybór - SelectionSort
Wnioski:
- algorytm ten jest bardzo kosztownym algorytmem
(klasa złożoności obliczeniowej – O(N
2
)
- nie nadaje się do porządkowania dużych zbiorów
- wykonuje taką samą ilość operacji porównania dla
zbiorów częściowo uporządkowanych jak i dla zbiorów
nieuporządkowanych
- algorytm przejrzysty, zwięzły
Algorytm sortowania bąbelkowego
Metoda porządkowania bąbelkowego swoją nazwę wzięła od
pęcherzyków powietrza ulatujących w górę tuby wypełnionej
wodą. Metoda ta polega na analizowaniu dwóch sąsiadujących
ze sobą elementów, jeśli nie są one uporządkowane następuje
ich zamiana.
40
2
2
2
2
2
2
2
40
4
4
4
4
4
39
4
40
6
6
6
6
6
39
6
40
18
18
18
18
6
39
18
40
20
20
4
18
18
39
20
40
39
20
20
20
20
39
39
40
Indeks tablicy
Etapy
Algorytm sortowania bąbelkowego
Dane:
n - liczba elementów zbioru,
d[ ] – zbiór sortowany. Elementy zbioru mają indeksy od
1 do n.
Wynik:
Uporządkowany zbiór d[ ]
Algorytm: porządkowanie bąbelkowe
Krok 1.
Dla j = n - 1, n - 2, ..., 1: wykonuj K02...K04, zakończ
algorytm
Krok 2.
p ← 1
Krok 3.
Dla i = 1, 2, ..., j: jeśli d[i] > d[i + 1], to d[i] ↔ d[i + 1];
p ← 0
Krok 4.
Jeśli p = 1, to zakończ
Algorytm sortowania bąbelkowego
for(j = N - 1; j > 0; j--)
{
p = 1;
for(i = 0; i < j; i++)
{
if(d[i] > d[i + 1])
{
swap(d[i],
d[i + 1]); p = 0;
}
}
if(p) break;
}
Algorytm sortowania bąbelkowego
Wnioski:
- algorytm ten jest bardzo kosztownym algorytmem
(klasa złożoności obliczeniowej – O(N
2
)
- bardzo prosta i zrozumiała struktura zapisu
- dość często zdarzają się puste przebiegi (brak
wykonania wymiany jeżeli elementu są
uporządkowane)
Rekurencja
Rekurencja - jest modą programowania polegająca na
wywoływaniu funkcji programu przez samą siebie .
Przykład:
long int silnia(int x)
{
if (x==0)
{
return 1;
}
else
{
return x * silnia(x-1);
}
}
Szybkie sortowanie - quicksort
Algorytm ten jak sama nazwa wskazuje, poprzez odpowiednią
dekompozycję osiągnął znaczny zysk w szybkości
porządkowania zbiorów.
Metoda szybkiego sortowania podzielona została na dwie części:
• część służąca do właściwego sortowania polegająca na
wywoływaniu samej siebie
• część odpowiadająca za rozdzielenie elementów tablicy
wartości osiowej podziału
P
< P
P
>= P
Szybkie sortowanie - quicksort
2
9
4
0
2
1
6
1
8
2
0
3
2
2
3
3
4
3
9
4
1
29
2
1
6
1
8
2
0
2
3
4
0
3
2
3
4
3
9
4
1
2
1
6
1
8
2
0
2
3
40
3
2
3
4
3
9
41
Szybkie sortowanie - quicksort
Oznaczenia:
left – lewy skrajny element
right – prawy skrajny element
p – wartość osiowa
i – zmienna sterująca pętlą
m – poszukiwany indeks komórki tablicy, w
której
umieszczamy element osiowy
Szybkie sortowanie - quicksort
void qsort(int* d, int left, int right)
{
if (left < right)
{
int m = left;
for(int i = left+1; i <= right; i++)
if (d[i] < d[left]) swap(d[++m],d[i]);
swap(d[left], d[m]);
qsort(d, left, m-1);
qsort(d, m+1, right);
}
}
Szybkie sortowanie - quicksort
Wnioski:
- dzięki zastosowaniu metody programowania „dziel
i zwyciężaj” algorytm w optymalnie krótkim czasie
realizuje
zadanie porządkowania zbiory
(klasa złożoności obliczeniowej – O(N log N)