Slajd 1

Spis treści

Sortowanie przez kopcowanie – Heap Sort

Sortowanie przez scalanie

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

1
8

2
0

Sortowanie przez scalanie – MergeSort

Etap scalania podzbiorów :

1
8

2
0

2
9

4
0

2
9

4
0

1
8

2
0

2
9

4
0

2
9

4
0

2
0

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

18 20 23 29 32 34 40

Szykana liczba: 2

2<20

2=20

2>20

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

Document Outline