Algorytmy sortowania
i porządkowania
Spis treści
1.
Sortowanie przez kopcowanie – Heap Sort
2.
Sortowanie przez scalanie
3.
Przeszukiwanie binarne
Sortowanie przez kopcowanie – Heap
Sort
Metoda ta jest drzewem binarnym zawierającym liczby lub
dowolne inne elementy dającego się porządkować zbioru.
Cechą kopca jest przedstawiony kształt oraz uporządkowanie
(każda wartość w węźle jest mniejsza od swojego rodzica
T[rodzic(i)] >= T[i])
Sortowanie przez kopcowanie- Heap
Sort
Reprezentacja kopca w tablicy T:
* Wierzchołek kopca wstaw do T[0]
* Dla dowolnego węzła w T[i] jego lewe dziecko
wstaw
do T[2i + 1], a jego prawe dziecko wstaw
do T[2i + 2]
Sortowanie przez kopcowanie – Heap
Sort
Sposób reprezentacji algorytmu:
1.Ułóż dane w kopiec (ułożenie w tablicy o rozmiarze n)
2.Usuń wierzchołek z kopca przez zamianę go z ostatnim
liściem drzewa (n--)
3.Przywróć własność kopca dla pozostałej części kopca (zadanie
realizowane jest z pominięciem usuniętego elementu)
4.Idź do punktu 2
Szczegółowa prezentacja punktu 3:
1.Jeżeli wierzchołek jest większy od obojga rodziców wyjdź
2.Zmień wierzchołek z większym dzieckiem
3.Przywróć własność kopca w części gdzie nastąpiła zmiana
Sortowanie przez kopcowanie – Heap
Sort
void przywroc(int T[], int k, int n)
{
int i,j;
i = T[k - 1];
while (k <= n/2)
{
j = 2 * k;
if (j < n && T[j-1] < T[j]) j++;
if (i >= T[j-1]) break;
else
{
T[k-1] = T[j-1];
k = j;
}
}
T[k-1] = i;
}
Implementacja funkcji przywracania:
Sortowanie przez kopcowanie – Heap
Sort
void hapesort(int T[], int n)
{
int k,tmp;
for (k = n/2; k > 0; k--) przywroc(T, k, n);
do
{
tmp = T[0];
T[0] = T[n-1];
T[n-1] = tmp;
n--;
przywroc(T, 1, n);
}
while (n > 1);
}
Implementacja funkcji sortującej:
Sortowanie przez kopcowanie – Heap
Sort
Wnioski:
- algorytm szybki i mało obciążający pamięć
- klasa złożoności obliczeniowej algorytmu – O(N log N)
- mało czuły na postać danych wejściowych
- doskonale nadaje się do porządkowania dużych
zbiorów
- implementacja mało czytelna
Sortowanie przez scalanie - MergeSort
Metoda porządkowania przez scalanie podobnie jak metoda
QuickSort należy do algorytmów porządkowania
wykorzystujących rekurencję
Algorytm ten polega na dzieleniu zbioru danych na podzbiory, aż
do uzyskania n zbiorów jednoelementowych (dzielenie następuje
bez sprawdzania warunków co skutkuje rozwinięciem wszystkich
węzłów).
Po rozwinięciu zbioru następuje scalanie poszczególnych
elementów poprzez odpowiednie wybieranie podzbiorów.
Sortowanie przez scalanie – MergeSort
Etap rozkładu zbioru na podzbiory:
2
9
4
0
2
1
1
8
2
0
2
9
4
0
2
1
1
8
2
0
2
9
4
0
2
2
9
4
0
2
0
1
1
8
1
1
8
Sortowanie przez scalanie – MergeSort
Etap scalania podzbiorów :
1
2
1
8
2
0
2
9
4
0
2
2
9
4
0
1
1
8
2
0
2
9
4
0
2
2
9
4
0
2
0
1
1
8
1
1
8
Sortowanie przez scalanie – MergeSort
Sposób reprezentacji algorytmu:
1.Dzielenie n – elementowego ciągu na dwa podciągi po n/2
elementów
2.Sortowanie każdego z podciągów
3.Łączenie posortowanych podciągów w jeden zbiór
Sortowanie przez scalanie – MergeSort
Reprezentacja algorytmu za pomocą listy kroków:
Dane:
T[ ] – zbiór do posortowania
Wynik:
Uporządkowany zbiór T[ ] w postaci rosnącej
Zmienne pomocnicze:
p, k, mid
Algorytm: porządkowanie przez scalanie MergeSort
Krok 1.
Jeżeli p<k, wylicz środek mid = (p+k)/2
Krok 2.
wykonaj algorytm MargeSort(T, p, mid)
Krok 3.
wykonaj algorytm MargeSort(T, mid+1,k)
Krok 4.
wykonaj algorytm scalania dla podzbiorów, a wynik
umieść w T
Sortowanie przez scalanie – MergeSort
void MergeSort(int T[], int p, int k)
{
if (p < k)
{
int mid = (p + k)/2;
MergeSort(T, p, mid);
MergeSort(T, mid + 1, k);
Scalaj(T, p, mid, k);
}
}
Implementacja funkcji sortującej:
Sortowanie przez scalanie – MergeSort
void Scalaj(int T[], int p, int mid, int k)
{
int T2[N];
int p1 = p, k1 = mid;
int p2 = mid + 1, k2 = k;
int i = p1;
while (p1 <= k1 && p2 <= k2)
{
if (T[p1] < T[p2])
{
T2[i] = T[p2];
p1++;
}
…
Implementacja funkcji scalającej:
…
else
{
T2[i] = T[p2];
p2++;
}
i++;
}
while (p1 <= k1)
{
T2[i] = T[p1];
p1++;
i++;
}
…
Sortowanie przez scalanie – MergeSort
Implementacja funkcji scalającej cd:
…
while (p2 <= k2)
{
T2[i] = T[p2];
p2++;
i++;
}
for(i = p; i <= k; i++) T[i] = T2[i];
}
Sortowanie przez kopcowanie – Heap
Sort
Wnioski:
- algorytm szybki
- prosty w zrozumieniu
- klasa złożoności obliczeniowej algorytmu – O(N log N)
- algorytm bardzo obciążający pamięć
- ze względu na duże zużycie pamięci algorytm słabo
nadaje
się do porządkowania dużych zbiorów
- złożona implementacja scalania
Algorytm wyszukiwania binarnego
Metoda wyszukiwania przez połowienie realizowana jest w
oparciu
o uporządkowane zbiory. Ideą tego algorytmu jest dzielenie
zbioru na dwie części i wybranie do dalszego przeszukiwania
tej połowy ,
w której liczba wyszukiwana może się znajdować
Algorytm wyszukiwania binarnego
1
2
6
18 20 23 29 32 34 40
Szykana liczba: 2
2<20
2=20
2>20
1
2
6
18
2<2
2=2
2>2
Algorytm wyszukiwania binarnego
Sposób reprezentacji algorytmu:
Dane:
Uporządkowany zbiór T[ ], y – szukany element
Wynik:
wartość -1 jeżeli szukiwanej wartości y brak w zbiorze
lub wartość określająca indeks komórki w której została
znaleziona wartość y
Algorytm: wyszukiwanie binarne
Krok 1.
Lewy= k, Prawy = l
Krok 2.
Jeżeli lewy > prawy to wypisz -1 i zakończ
Krok 3.
wylicz Srodek = (Lewy + Prawy)/2
Jeżeli T[Srodek] = y, to wypisz Srodek i zakończ
Jeżeli T[Srodek] < y, to lewy = Srodek + 1, a w
przeciwnym
wypadku Prawy = Srodek - 1
Algorytm wyszukiwania binarnego
Implementacja funkcji:
:
int PrzeszukiwanieBinarne(int a[], int k, int l, int y)
{
int Srodek, Lewy, Prawy;
Lewy=k; Prawy=l;
while (Lewy<=Prawy)
{
Srodek=(Lewy+Prawy)/2;
if (a[Srodek]==y){ return Srodek; break;}
else if (a[Srodek]<y) Lewy=Srodek+1;
else Prawy=Srodek-1;
}
return -1;
}
Algorytm wyszukiwania binarnego
Rekurencyjna implementacja funkcji:
:
int PrzeszukiwanieBinarne(int a[], int k, int l, int y)
{
int Srodek, Lewa, Prawa;
Lewa=k; Prawa=l;
if (Lewa>Prawa) return -1;
else
{
Srodek=(Lewa+Prawa)/2;
if (a[Srodek]==y) return Srodek;
else if (a[Srodek]>y) return
PrzeszukiwanieBinarne(a,k,Srodek-1,y);
else return PrzeszukiwanieBinarne(a,Srodek+1,l,y);
}
}
Algorytm wyszukiwania binarnego
Wnioski:
- algorytm szybki (klasa złożoności obliczeniowej
O(log2 N)
- prosty w zrozumieniu
- prosta i czytelna implementacja algorytmu