Cvičenie č.9

Ciele

Porozumieť dodanej implementácii algoritmov triedenia založených na porovnávaní.
Podľa dodaného pseudokódu implementovať algoritmus triedenia BubbleSort.
Podľa dodaného pseudokódu implementovať algoritmus triedenia InsertionSort.

Úvod

Návrh a implementácia algoritmov triedenia založených na porovnávaní triedených prvkov.

Postup

Implementácia efektívnych triediacich algoritmov HeapSort a QuickSort.

Poznámka: Činnosť vybraných algoritmov triedenia porovnávaním je možné sledovať na tejto stránke.

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte a výsledný program spustite.

Pripravený archív obsahuje tieto súbory:
- quicksort.h - definičný modul algoritmu QuickSort.
- quicksort.c - implementačný modul algoritmu QuickSort.
- heapsort.h - definičný modul algoritmu HeapSort.
- heapsort.c - implementačný modul algoritmu HeapSort.
- test.c - modul pre testovanie. Obsahuje aj funkciu main.
Poznámka: V prípade algoritmu HeapSort je možné zapnúť postupné zobrazovanie stavu haldy (heap) volaním funkcie hsortDebug(1). Vypnutie zobrazovania sa realizuje volaním hsortDebug(0) - v prípade rozsiahleho vstupu sa doporučuje tento režim. Podobne, pre sledovanie činnosti algoritmu QuickSort je možné použiť volanie qsortDebug(1) (obrázok).

Poznámka: Dôkladne preštudujte dodaný kód. V prípade nejasností sa s konkrétnou otázkou obráťte na cvičiaceho.
Implementácia algoritmu BubbleSort.

Úloha: Implementujte algoritmus BubbleSort (napr. podľa uvedeného pseudokódu).

Opis: Triedenie s využitím porovnania susedných prvkov.
Vstup: postupnosť prvkov, Výstup: utriedená postupnosť prvkov.
```
procedure bubbleSort( A : list of sortable items ):
  for each i in 1 to length(A) do:
     for each j in length(A) downto i + 1 do:
       if A[ j - 1  ] > A[ j ] then
         swap( A[ j - 1],  A[ j ] )
       end if
     end for
  end for
end procedure
            
```
Úloha: Postupne zobrazujte činnosť algoritmu (stav poľa) po každom prechode hlavným cyklom.

Úloha: Pridajte podporu utriedenia vstupnej postupnosti vzostupne a zostupne podľa hodnoty parametra funkcie realizujúcej triedenie (pozri obrázok).
Implementácia algoritmu InsertionSort.

Úloha: Implementujte algoritmus InsertionSort (napr. podľa uvedeného pseudokódu).

Opis: Triedenie vkladaním s využitím porovnania.
Vstup: postupnosť prvkov, Výstup: utriedená postupnosť prvkov.
```
insertionSort(array A)
    for i ← 1 to length[A]-1 do
        value ← A[i]
        j ← i-1
        while j >= 0 and A[j] > value do
            A[j + 1] ← A[j]
            j ← j-1
        A[j+1] ← value
            
```
Úloha: Postupne zobrazujte činnosť algoritmu (stav poľa) po každom prechode hlavným cyklom.

Úloha: Pridajte podporu utriedenia vstupnej postupnosti vzostupne a zostupne podľa hodnoty parametra funkcie realizujúcej triedenie (pozri obrázok).

Poznámka: Algoritmy BubbleSort a InsertionSort sú menej efektívne (dlhší čas behu algoritmu pre vyššie počty triedených prvkov).

Doplňujúce úlohy

Úloha: Implementujte algoritmus MergeSort.