Cvičenie 5 – Triedenie

Ciele cvičení:

  • rozumieť princípom algoritmov QuickSort, MergeSort a HeapSort a vedieť analyzovať ich časovú zložitosť
  • spoznať údajovú štruktúru halda

QuickSort

Uvažujme triedu TriediaciAlgoritmus (nižšie). Rozšírením tejto triedy vytvorte triedu QuickSort, ktorá bude implementovať tento algoritmus prekrytím metódy utried.

Ďalšie úlohy:

  • S využitím knižnice CallTree preskúmajte štruktúru rekurzívnych volaní.
    • Ako vyzerá strom volaní?
    • Aký je obsah poľa pri jednotlivých volaniach?
    • Koľko porovnaní sa vykoná?
  • Nájdite taký vstup pre vašu implementáciu algoritmu QuickSort, aby časová zložitosť QuickSort-u na tomto vstupe bola minimálna (O(n.log n) – zdôvodnite). Viete podať algoritmus, ako takýto vstup vytvoriť pre zadanú množinu hodnôt?
  • Nájdite taký vstup pre vašu implementáciu algoritmu QuickSort, aby časová zložitosť QuickSort-u na tomto vstupe bola maximálna (Ɵ(n2) – zdôvodnite).
  • Čo viete povedať o modifikovanom algoritme, v ktorom sa pivot nevolí ako prvý (či prostredný) prvok podpoľa, ale ako náhodný prvok v podpoli (implementujte). Tento algoritmus nazývame pravdepodobnostný (randomizovaný) QuickSort.

Vyzeráš ako strom v poli

  • Nakreslite takmer úplný binárny strom pre 10 náhodne zvolených čísel (od 1 po 30).
  • Zakreslite tento strom do poľa s 10 políčkami po úrovniach tak, ako to bolo ukázané na prednáške.
  • Strom v poli dajte kolegovi a požiadajte ho, aby našiel hodnotu v strome, ktorá je pravým synom ľavého syna koreňa (cesta: LR). Ďalej ho požiadajte, aby našiel hodnotu na ceste od koreňa RL (najprv pravý syn, potom ľavý syn). Popíšte aj navigačnú cestu k nejakému ďalšiemu uzlu v strome a požiadajte ho, aby hodnotu v tomto uzle našiel.
  • Predpokladajme, že pole p uchováva hodnoty takmer úplného binárneho stromu (spôsobom, ako bolo ukázané na prednáške). Reťazec cesta nech obsahuje navigačnú cestu so začiatkom v koreni stromu, ktorá je tvorená písmenami L (presuň sa do ľavého syna) a R (presuň sa do pravého syna). Implementujte metódu, ktorá vráti hodnotu v uzle stromu určenom zadanou navigačnou cestou.


1
public static int hodnotaVStrome(int[] pole, String cesta)
  • Je nakreslený strom haldou?
  • Vytvorte metódu, ktorá overí, či takmer úplný binárny strom uložený v poli je haldou.


1
public static boolean jeHaldou(int[] pole)

Zlučovanie usporiadaných postupností a MergeSort

  • Vytvorte 2 usporiadané (napr. 5-prvkové) postupnosti čísel. Aplikovaním algoritmu z prednášky zlúčte tieto 2 postupnosti do 10-prvkového usporiadaného poľa.
  • Naprogramujte metódu, ktorá zrealizuje spojenie dvoch utriedených polí p1 a p2 do utriedeného výsledného poľa. Aká je jej časová zložitosť?


1
public static int[] zluc(int[] p1, int[] p2);
  • Vyskúšajte odsimulovať algoritmus MergeSort z prednášky na utriedenie poľa 10 hodnôt. Rozdiskutujte aj časovú zložitosť algoritmu.

HeapSort

Poznámka: pri jednotlivých operáciach si všímajte ako sa mení obsah poľa uchovávajúceho takmer úplný binárny strom v závislosti od zmeny obsahu v strome.

  • Nakreslite takmer úplný binárny strom pre 10 náhodne vybraných čísel (od 1 po 30).
  • Je zakreslený strom haldou?
  • Nakreslite hodnoty do stromu tak, aby bola splnená vlastnosť haldy.
  • Zmeňte hodnotu v koreni na náhodné menšie číslo. Aplikujte algoritmus z prednášky, aby sa strom opäť stal haldou. Aká je časová zložitosť tohto algoritmu?
  • Vyskúšajte si odsimulovať algoritmus na vybudovanie haldy z prednášky aplikovaním na 10 náhodných hodnôt. Zdôvodnite celkovú časovú zložitosť vybudovania haldy.
  • Po vybudovaní haldy aplikujte algoritmus z prednášky na utriedenie poľa. Zdôvodnite celkovú časovú zložitosť utriedenia hodnôt pomocou haldy.
  • Pre pokročilých: Dokážte, že časová zložitosť vytvorenia n-prvkovej haldy je O(n)

Prioritný rad

  • Implementujte prioritný rad čísel (priorita čísla je jeho hodnota) s obmedzenou maximálnou kapacitou:


1
2
3
4
5
6
public class PrioritnyRad {

    public PrioritnyRad(int kapacita);

    public boolean offer(int cislo);

    public int poll();

    public boolean isEmpty();

}

Prioritný rad je rad, v ktorom metóda poll vráti najväčšie číslo v rade. Ak je takých čísel viac, vráti ľubovoľné z nich. Triedu implementujte tak, aby žiadna z operácií nemala trvanie dlhšie ako O(log(n)), kde n je počet hodnôt uložených v rade. Obmedzenie na kapacitu určuje, že v rade nemôže čakať viac hodnôt, než je zadaná kapacita radu.

Pozri, čo som našiel na webe

Pozrite si niektorú z týchto implementácií QuickSortu:

V čom je táto implementácia iná? V čom sa líši operácia rozdeľovania podľa pivota? Aká je časová zložitosť rozdeľovania podľa pivota v týchto implementáciách?

Dolné ohraničenie pre triedenie (pre fajnšmekrov)

  • Označme si M(h) maximálny počet listov v binárnom strome s výškou h. Určte hodnotu M(h) s využitím vzťahu M(h) = 2*M(h-1), ktorý vyplýva z toho, že strom s maximálnym počtom listov a výškou h vieme vybudovať z 2 stromov s maximálnym počtom listov a výškou h-1. Presnú hodnotu M(h) dokážte matematickou indukciou vzhľadom na h.
  • Analyzujte rozhodovacie stromy pre triediaci algoritmus založený na porovnávaní, ktorý usporadúva postupnosti dĺžky n. Aký je minimálny počet listov v tomto strome?
  • S využitím Stirlingovej formuly ukážte, že výška v rozhodovacom strome (a tým aj minimálny počet porovnaní) musí byť aspoň Omega(n.log(n)).

Medián v čase O(n) (pre fajnšmekrov)

Rozdiskutujte algoritmus na nájdenie mediána postupnosti v lineárnom čase.

Trieda TriediaciAlgoritmus



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.Arrays;



public abstract class TriediaciAlgoritmus {



    /**

     * Aktualne usporiadavane pole

     */

    private int[] p;



    /**

     * Porovna prvky v poli na zadanych indexoch

     *

     * @return vrati zaporne cislo, ak p[idx1] < p[idx2], * 0, ak p[idx1]==p[idx2], a * kladne cislo, ak p[idx1] > p[idx2]

     */

    protected int porovnaj(int idx1, int idx2) {

        return Integer.compare(p[idx1], p[idx2]);

    }



    /**

     * Vymeni prvky v usporiadavanom poli na zadanych indexoch

     */

    protected void vymen(int idx1, int idx2) {

        int pom = p[idx1];

        p[idx1] = p[idx2];

        p[idx2] = pom;

    }



    /**

     * Vypise pole

     */

    protected void vypisPole() {

        System.out.println(Arrays.toString(p));

    }



    /**

     * Usporiada prvky v poli od najmensieho po najvacsie

     *

     * @param p

     *            pole, ktoreho prvky maju byt usporiadane

     */

    public void utried(int[] p) {

        this.p = p;

        utried(p.length);

        this.p = null;

    }



    /**

     * Metoda, ktora implementuje triedenie podla urciteho algoritmu

     * @param dlzkaPola dlzka (pocet prvkov) usporiadavaneho pola

     */

    protected abstract void utried(int dlzkaPola);

}