Cvičenia: 5. týždeň

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:

  • Rozšírte implementáciu o informačné výpisy (napr. aké rekurzívne volania sa realizujú, ako vyzerá obsah poľa po jednotlivých krokoch) a počítadlo porovnaní.
  • 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.
public static int hodnotaVStrome(int[] pole, String cesta)
[$[Get Code]]
  • Je nakreslený strom haldou?
  • Vytvorte metódu, ktorá overí, či takmer úplný binárny strom uložený v poli je haldou.
public static boolean jeHaldou(int[] pole)
[$[Get Code]]

Zlučovanie usporiadaných postupností a MergeSort

  • Vytvorte 2 usporiadané (napr. 5-prvkové) postupnosti čísel. Aplikovaním algoritmus 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ť?
public static int[] zluc(int[] p1, int[] p2);
[$[Get Code]]
  • 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 ú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:
public class PrioritnyRad {
        public PrioritnyRad(int kapacita);
        public boolean offer(int cislo);
        public int poll();
        public boolean isEmpty();
}
[$[Get Code]]
Prioritný rad je rad, v ktorom metóda pool 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 (E[xtra] skupina)

  • 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) (E[xtra] skupina)

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

Trieda TriediaciAlgoritmus

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 p[idx1] - p[idx2];

                /*
                 * Alternativa:
                 * if (p[idx1] < p[idx2]) return -1;
                 * if (p[idx1] > p[idx2]) return 1;
                 * return 0;
                 */
        }

        /**
         * 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() {
                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);
}
[$[Get Code]]