Programovanie (2) v Jave
1-INF-166, LS 2016/17

Úvod · Pravidlá · Prednášky · Projekt · Netbeans · Odovzdávanie · Test a skúška
· Vyučujúcich môžete kontaktovať pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· Predvádzanie projektov bude v pondelok 5.6. od 9:00 do 12:00 a v utorok 6.6 od 12:00 do 13:30 (po skúške), oboje v miestnosti M217. Na termín sa prihláste v AIS. Ak robíte vo dvojici, prihlási sa iba jeden člen dvojice.
· Body zo záverečného testu sú na testovači. Poradie príkladov: P1: do šírky, P2: topologické, P3: výnimky, P4: iterátor, P5: testy, P6: strom. Bolo potrebné získať aspoň 20 bodov zo 40.
· Opravný test bude 19.6.2017 od 9:00 v miestnosti M-I. Na termín sa prihláste v AISe.
· Zapisovanie známok a osobné stretnutia ku skúške budú v utorok 13.6. 13:30-14:30 v M163 a v stredu 14.6. 14:00-14:30 v M163.


Prednáška 6

Z Programovanie
Prejsť na: navigácia, hľadanie

Organizačné poznámky

  • Termín DU3 je 10.10. do 22:00.
  • Ak má ešte niekto problém s Netbeans pod Windows, pošlite mail Jane Katreniakovej.
  • Na doplnkovom cvičení opravná rozcvička (body z rozcvičky sa objavia, ak niekomu budú chýbať máme nejaké nepodpísané).
  • Prebrali sme premenné, polia, podmienky, cykly a funkcie.
    • Z týchto stavebných prvkov sa dajú vystavať pomerne komplikované programy. Menej skúsení programátori si potrebujú prácu s týmito pojmami čo najviac precvičiť. Skúste si vyriešiť všetky príklady z cvičení. Kontaktujte nás, ak Vám niečo nie je jasné.
    • Predbežný plán: tento a budúci týždeň algoritmy s poliami, znaky a reťazce. Ďalší týždeň potom začneme rekurziu (veľa študentom robila problém na skúške).

Parametre funkcií - prehľad, opakovanie

  • Jednoduché typy, napr. int, double, bool
    • Bez & sa skopíruje hodnota
    • S & premenná dostane vo funkcii nové meno
void f1(int x) {
    x++; // zmena x sa nepresenie do main (y zostane rovnaká)
    cout << x << endl;
}

void f2(int &x) {
    x++; // zmena x sa prenesie ako zmena y v main
    cout << x << endl;
}

int main(void) {
    int y = 0;
    f1(y);
    f2(y);
    f1(y + 1);
    //zle: f2(y+1);
}
  • Polia odovzdávame bez &
    • väčšinou potrebujeme poslať aj veľkosť poľa, ak nie je globálne známa
    • zmeny v poli zostanú aj po skončení funkcie
void f(int a[], int n) {
    for (int i = 0; i < n; i++) {
        cout << a[i] << endl;
    }
}

int main(void) {
    int b[3] = {1, 2, 3};
    f(b, 3);
}
  • Turtle a SVGdraw obrázok sú v skutočnosti objekty, väčšinou ich chcete posielať s &
    • všetky zmeny na nich spravené pretrvávajú aj po skončení funkcie
void kresli(Turtle &t, int n) {
  for(int i=0; i<n; i++) {
     t.turnLeft(rand() % 360);
     t.forward(10);
  }
}
int main(void) {
    int n=10;    
    Turtle turtle(500, 500, "chod.svg", window, 250, 450, 0);
    kresli(turtle, n);
    turtle.finish();
}
  • Štruktúry (struct) väčšinou tiež posielame pomocou &
  • Návratové hodnoty:
    • ak je výsledkom funkcie jedno číslo alebo pravdivostná hodnota, vrátime ju príkazom return
    • ak je výsledkom viac hodnôt, alebo niečo zložitejšie (pole, struct,...), odovzdáme ho ako parameter pomocou &, návratová hodnota môže zostať void
  • Tieto pravidlá súvisia so smerníkmi a správou pamäti, povieme si viac o pár týždňov

Polynómy

  • Príklad polynómu: 2x^{3}+3x-1.
  • Polynóm si môžeme uložiť do poľa, pričom koeficient pri x^{i} dáme do a[i]
  • Pre náš príklad vytvoríme pole napríklad príkazom double a[4] = {-1, 3, 0, 2};
  • Teraz si ukážeme niekoľko funkcií, ktoré s polynómami pracujú.

Vyhodnocovanie polynómu

  • Chceme spočítať hodnotu polynómu pre nejaké konkrétne x
  • Príklad: pre 2x^{3}+3x-1 a pre x=2 dostaneme 21=(2\cdot 2^{3}+3\cdot 2-1)

Pokus 1:

double evaluatePolynomial(double a[], int n, double x) {
    /* a je pole koeficientov s n hodnotami.
     * Funkcia vráti hodnotu tohto polynómu v bode x.
     *
     * Táto implementácia na výpočet x na i používa funkciu
     * pow, čo ale pomalé a potenciálne nie úplne presné.
     */
    double value = 0;
    for (int i = 0; i < n; i++) {
        value += a[i] * pow(x, i);
    }
    return value;
}
  • Pripomíname: value += x je to isté ako value = value + x
  • Všimnite si, že v komentári na začiatku funkcie popisujeme, čo tá funkcia robí, to je väčšinou dobrý nápad spraviť.
  • Aký najvyšší stupeň môže mať polynóm a (ako funkcia n)?

Pokus 2:

  • Vyhneme sa volaniu pow tým, že budeme nejakú premennú opakovanie násobiť hodnotou x
  • V cykle uvádzame ako komentár invariant, podmienku, ktorá na tom mieste vždy platí. Takýto invariant nám pomôže si uvedomiť, že je náš program správny.
  • Čo by sa stalo, ak by sme prehodili dva príkazy vo vnútri cyklu?
double evaluatePolynomial(double a[], int n, double x) {
    /* a je pole koeficientov s n hodnotami.
     * Funkcia vráti hodnotu tohto polynómu v bode x.
     *
     * Táto implementácia počíta x na i v cykle spolu
     * s vyhodnocovaním polynómu.
     */
    double value = 0;
    double xpow = 1;
    for (int i = 0; i < n; i++) {
        /* Invariant: xpow sa rovna x na i */
        value += a[i] * xpow;
        xpow *= x;
    }
    return value;
}

Pokus 3: Hornerova schéma

  • O kúsoček lepšia ako pokus 2 - nepotrebuje pomocnú premennú a v každej iterácii cyklu robí iba jedno násobenie, nie dve
  • Idea je začať od najvyšších mocnín x:
    • 2x^{3}+0x^{2}+3x-1=((2\cdot x+0)x+3)x-1
double evaluatePolynomial(double a[], int n, double x) {
    /* a je pole koeficientov s n hodnotami.
     * Funkcia vráti hodnotu tohto polynómu v bode x.
     *
     * Táto implementácia používa tzv. Hornerovu schému,
     * ktorá začína od najvyšších koeficentov a
     * a pre každé i robí iba jedno sčítanie a jedno násobenie.
     */
    double value = 0;
    for (int i = n - 1; i >= 0; i--) {
        value = value * x + a[i];
    }
    return value;
}

Cvičenie: aký je invariant po vykonaní príkazu v cykle?


Hlavný program:

#include <cstdlib>
#include <cmath>
#include <iostream>
using namespace std;

double evaluatePolynomial(double a[], int n, double x) {
  // jedna z funkcií vyššie
}

void enterPolynomial(double a[], int &n, int maxN) {
    /* Od užívateľa načíta koeficienty polynómu do a,
     * ich počet uloží do n, maxN je veľkosť poľa,
     * ktorú nemožno prekročiť. */
    cout << "Zadaj pocet koeficientov n: ";
    cin >> n;
    if (n > maxN) {
        cout << "Prilis velke n!" << endl;
        exit(1);
    }
    for (int i = 0; i < n; i++) {
        cout << "Zadaj koeficient pri x na " << i << ": ";
        cin >> a[i];
    }
}

int main(void) {
    const int maxN = 100;
    int n;
    double a[maxN];

    enterPolynomial(a, n, maxN);
    double x;
    cout << "Zadaj x: ";
    cin >> x;
    cout << "Hodnota pre x=" << x << " je " << evaluatePolynomial(a, n, x) << endl;
}
Zadaj pocet koeficientov n: 4
Zadaj koeficient pri x na 0: -1
Zadaj koeficient pri x na 1: 3
Zadaj koeficient pri x na 2: 0
Zadaj koeficient pri x na 3: 2
Zadaj x: 2
Hodnota pre x=2 je 21

Sčítanie polynómov

  • Pri sčítaní polynómov len sčítame koeficienty pri zodpovedajúcich mocninách x
  • Napr. (2x^{3}+3x-1)+(-4x^{2}+2x+7)=(2+0)x^{3}+(0-4)x^{2}+(3+2)x^{1}+(-1+7)x^{0}=2x^{3}-4x^{2}+5x+6
  • Musíme dávať pozor na to, že dĺžky polynómov môžu byť rôzne a hodnoty v poli za n ďalej sú nedefinované.
void addPolynomials(double a[], int na, double b[], int nb, double c[], int &nc) {
    /* a je pole koeficientov polynomu s na hodnotami,
     * b je pole koeficientov s nb hodnotami
     * do c zratame ich sucet, do nc pocet hodnot, ktory bude vacsie z
     * na, nb. Predpokladame, ze c je dost velke, aby sa do neho nc
     * prvkov zmestilo. */
    if (na > nb) {
        nc = na;
    } else {
        nc = nb;
    }

    for (int i = 0; i < nc; i++) {
        c[i] = 0;
        if (i < na) {
            c[i] += a[i];
        }
        if (i < nb) {
            c[i] += b[i];
        }
    }
}

Hlavný program: (teraz vidíme, načo nám je funkcia enterPolynomial, bez nej by sme cyklus na načítavanie museli písať dvakrát)

#include <cstdlib>
#include <iostream>
using namespace std;

void enterPolynomial(double a[], int &n, int maxN) {
  // pozri vyššie
}

void writePolynomial(double a[], int n) {
    /* a je pole koeficientov polynómu s n hodnotami */
    for (int i = 0; i < n; i++) {
        cout << "Koeficient polynomu pri x na " << i << " je " << a[i] << endl;
    }
}

int main(void) {
    const int maxN = 100;
    int na, nb;
    double a[maxN], b[maxN];
 
    cout << "Prvy polynom:" << endl;
    enterPolynomial(a, na, maxN);
    cout << endl << "Druhy polynom:" << endl;
    enterPolynomial(b, nb, maxN);

    double c[maxN];
    int nc;
    addPolynomials(a, na, b, nb, c, nc);
    cout << endl << "Ich sucet:" << endl;
    writePolynomial(c, nc);
}

Príklad behu:

Prvy polynom:
Zadaj pocet koeficientov n: 4
Zadaj koeficient pri x na 0: -1
Zadaj koeficient pri x na 1: 3
Zadaj koeficient pri x na 2: 0
Zadaj koeficient pri x na 3: 2

Druhy polynom:
Zadaj pocet koeficientov n: 3
Zadaj koeficient pri x na 0: 7
Zadaj koeficient pri x na 1: 2
Zadaj koeficient pri x na 2: -4

Ich sucet:
Koeficient polynomu pri x na 0 je 6
Koeficient polynomu pri x na 1 je 5
Koeficient polynomu pri x na 2 je -4
Koeficient polynomu pri x na 3 je 2

Ďalšie príklady s polynómami

Vieme napísať aj ďalšie funkcie alebo programy na prácu s polynómami:

  • Vykresľovanie grafu (rátame hodnotu polynómu v husto rozmiestnených bodoch)
  • Násobenie polynómov
  • Delenie so zvyškom a Euklidov algoritmus
  • Derivácia
  • A mnohé ďalšie

Načo sú v programovaní dobré funkcie

  • Rozbijeme veľký problém na menšie dobre definované časti (napr. načítaj polynóm, spočítaj jeho hodnotu), každou časťou sa môžeme zaoberať zvlášť. Výsledný program je ľahšie pochopiteľný, najmä ak u každej funkcie napíšeme, čo robí.
  • Vyhneme sa opakovaniu kusov kódu (napr. načítanie polynómu A a B). Pri kopírovaní kusov kódu ľahko narobíme chyby, a ak chceme niečo meniť, musíme meniť na veľa miestach.
  • Hotové funkcie môžeme použiť aj v ďalších programoch, prípadne z nich zostavovať nové knižnice, napríklad knižnicu na prácu s polynómami.

Triedenia

Máme pole čísel, chceme ich usporiadať od najmenšieho po najväčšie.

  • Napr. pre pole 9 3 7 4 5 2 chceme dostať 2 3 4 5 7 9
  • Jeden z najštudovanejších problémov v informatike.
  • Súčasť mnohých zložitejších algoritmov.
  • Veľa spôsobov, ako triediť, dnes si ukážeme zopár najjednoduchších.

Bublinkové triedenie (Bubble Sort)

Idea: Kontrolujeme všetky dvojice susedných prvkov a keď vidíme menšie číslo za väčším, vymeníme ich

       for (int i = 1; i < n; i++) {
            if (a[i] < a[i - 1]) {
                swap(a[i - 1], a[i]);
            }
        }
  • Ak sme nenašli v poli žiadnu dvojicu, ktorú treba vymeniť, skončili sme.
  • Inak celý proces opakujeme znova.

Celé triedenie:

void swap(int &x, int &y) {
    /* Vymeň hodnoty premenných x a y. */
    int tmp = x;
    x = y;
    y = tmp;
}

void sort(int a[], int n) {
    /* usporiadaj prvky v poli a od najmenšieho po najväčší */

    bool hotovo = false;
    while (!hotovo) {
        bool vymenil = false;
        /* porovnávaj všetky dvojice susedov, vymeň ak menší za väčším */
        for (int i = 1; i < n; i++) {
            if (a[i] < a[i - 1]) {
                swap(a[i - 1], a[i]);
                vymenil = true;
            }
        }
        /* ak sme žiadnu dvojicu nevymenili, môžeme skončiť. */
        if (!vymenil) {
            hotovo = true;
        }
    }
}
  • Čo ak vo for cykle dám for (int i = 0; i < n; i++) {
  • Ako nahradím premennú hotovo príkazom break?

Príklad behu:

prvá iterácia while cyklu
 9 3 7 4 5 2
 3 9 7 4 5 2
 3 7 9 4 5 2
 3 7 4 9 5 2
 3 7 4 5 9 2
 3 7 4 5 2 9

druhá iterácia while cyklu
 3 7 4 5 2 9
 3 4 7 5 2 9
 3 4 5 7 2 9
 3 4 5 2 7 9

tretia iterácia while cyklu
 3 4 5 2 7 9
 3 4 2 5 7 9

štvrtá iterácia while cyklu
 3 4 2 5 7 9
 3 2 4 5 7 9

piata iterácia while cyklu
 3 2 4 5 7 9
 2 3 4 5 7 9

Cvičenie: Ako sa bude správať algoritmus na nasledujúcich vstupoch, koľkokrát zopakuje vonkajší while cyklus?

  • Utriedené pole 1,2,...,n
  • Pole n,1,2,...,n-1
  • Pole 2,3,...,n,1
  • Pole n,n-1,...,1

Triedenie výberom (selection sort, max sort)

Idea: nájdime najväčší prvok a uložme ho na koniec. Potom nájdime najväčší medzi zvyšnými a uložme ho na druhé miesto odzadu atď.

int maxIndex(int a[], int n) {
    /* vráť index, na ktorom je najväčší prvok z prvkov a[0]...a[n-1] */
    int index = 0;
    for(int i=1; i<n; i++) {
        if(a[i]>a[index]) {
            index = i;
        }
        /* invariant: a[j]<=a[index] pre vsetky j=0,...,i*/
    }
    return index;
}

void sort(int a[], int n) {
    /* usporiadaj prvky v poli a od najmenšieho po najväčší */

    for(int kam=n-1; kam>=1; kam--) {
        /* invariant: a[kam+1]...a[n-1] sú utriedené
         * a pre každé i,j také že 0<=i<=kam, kam<j<n platí a[i]<=a[j] */
        int index = maxIndex(a, kam+1);
        swap(a[index], a[kam]);
    }
}

Príklad behu programu

Vstup           9 3 7 4 5 2 
Po výmene (9,2) 2 3 7 4 5 9
Po výmene (7,5) 2 3 5 4 7 9
Po výmene (5,4) 2 3 4 5 7 9
Po výmene (4,4) 2 3 4 5 7 9
Po výmene (3,3) 2 3 4 5 7 9

Cvičenie: Bude čas behu algoritmu výrazne odlišný pre pole utriedené správne a pole utriedené v opačnom poradí?

Triedenie vkladaním (Insertion Sort)

Idea:

  • v prvej časti poľa prvky v utriedenom poradí
  • zober prvý prvok z druhej časti a vlož ho na správne miesto v utriedenom poradí

Príklad behu algoritmu:

 9 3 7 4 5 2
 3 9 7 4 5 2
 3 7 9 4 5 2
 3 4 7 9 5 2
 3 4 5 7 9 2
 2 3 4 5 7 9

Ako spraviť vkladanie:

  • Vkladaný prvok si zamätáme v pomocnej premennej
  • Utriedené prvky posúvame o jedno doprava, kým nenájdeme správne miesto pre odložený prvok
void sort(int a[], int n) {
    /* usporiadaj prvky v poli a od najmenšieho po najväčší */

    for (int i = 1; i < n; i++) {
        int prvok = a[i];
        int kam = i;
        while (kam > 0 && a[kam - 1] > prvok) {
            a[kam] = a[kam - 1];
            kam--;
        }
        a[kam] = prvok;
    }
}
  • Všimnime si podmienku (kam > 0 && a[kam - 1] > prvok)
    • Ak kam==0, prvá časť je false, druhá časť sa už nevyhodnocuje
    • Ak by sme prehodili časti, program by mohol spadnúť (a[kam - 1] > prvok && kam > 0)

Cvičenie: Ako sa bude správať algoritmus na nasledujúcich vstupoch, koľkokrát zopakuje priradenie a[kam]=a[kam-1]?

  • Utriedené pole 1,2,...,n
  • Pole n,1,2,...,n-1
  • Pole 2,3,...,n,1
  • Pole n,n-1,...,1

Zhrnutie

  • Videli sme niekoľko nových algoritmov:
    • Vyhodnocovanie a sčítavanie polynómov
    • Tri jednoduché algoritmy na triedenie
      • Neskôr sa ešte naučíme rýchlejšie algoritmy na triedenie, ktoré používajú rekurziu
  • Precvičili sme si funkcie, parametre a polia
  • K funkciám je dobré napísať, čo robia
  • Do cyklov si môžeme písať invarianty
    • Používajú sa pri formálnom dokazovaní správnosti
    • Pomáhajú pochopeniu kódu
    • Môžeme ich použiť na ručnú alebo automatickú kontrolu správnosti hodnôt premenných
    • Príkaz assert v knižnici cassert kontroluje podmienku, napr. assert(i>=0 && i<n); ukončí program s chybovou hláškou ak podmienka neplatí

Zdrojový kód programu s polynómami

/* Program s polynómami z prednášky 6. 
   http://compbio.fmph.uniba.sk/vyuka/prog/index.php/Predn%C3%A1%C5%A1ka_6 */
#include <cstdlib>
#include <cmath>
#include <iostream>
using namespace std;

const int maxN = 100;

double evaluatePolynomialPow(double a[], int n, double x) {
    /* a je pole koeficientov s n hodnotami.
     * Funkcia vráti hodnotu tohto polynómu v bode x.
     *
     * Táto implementácia na výpočet x na i používa funkciu
     * pow, čo ale pomalé a potenciálne nie úplne presné.
     */
    double value = 0;
    for (int i = 0; i < n; i++) {
        value += a[i] * pow(x, i);
    }
    return value;
}

double evaluatePolynomialMult(double a[], int n, double x) {
    /* a je pole koeficientov s n hodnotami.
     * Funkcia vráti hodnotu tohto polynómu v bode x.
     *
     * Táto implementácia počíta x na i v cykle spolu
     * s vyhodnocovaním polynómu.
     */
    double value = 0;
    double xpow = 1;
    for (int i = 0; i < n; i++) {
        /* Invariant: pow sa rovna x na i */
        value += a[i] * xpow;
        xpow *= x;
    }
    return value;
}

double evaluatePolynomialHorner(double a[], int n, double x) {
    /* a je pole koeficientov s n hodnotami.
     * Funkcia vráti hodnotu tohto polynómu v bode x.
     *
     * Táto implementácia používa tzv. Hornerovu schému,
     * ktorá začína od najvyšších koeficentov a
     * a pre každé i robí iba jedno sčítanie a jedno násobenie.
     */
    double value = 0;
    for (int i = n - 1; i >= 0; i--) {
        value = value * x + a[i];
    }
    return value;
}

void addPolynomials(double a[], int na, double b[], int nb, double c[], int &nc) {
    /* a je pole koeficientov polynomu s na hodnotami,
     * b je pole koeficientov s nb hodnotami
     * do c zratame ich sucet, do nc pocet hodnot, ktory bude vacsie z
     * na, nb. Predpokladame, ze c je dost velke, aby sa do neho nc
     * prvkov zmestilo. */
    if (na > nb) {
        nc = na;
    } else {
        nc = nb;
    }

    for (int i = 0; i < nc; i++) {
        c[i] = 0;
        if (i < na) {
            c[i] += a[i];
        }
        if (i < nb) {
            c[i] += b[i];
        }
    }
}

void enterPolynomial(double a[], int &n, int maxN) {
    /* Od užívateľa načíta koeficienty polynómu do a,
     * ich počet uloží do n, maxN je veľkosť poľa,
     * ktorú nemožno prekročiť. */
    cout << "Zadaj pocet koeficientov n: ";
    cin >> n;
    if (n > maxN) {
        cout << "Prilis velke n!" << endl;
        exit(1);
    }
    for (int i = 0; i < n; i++) {
        cout << "Zadaj koeficient pri x na " << i << ": ";
        cin >> a[i];
    }
}

void writePolynomial(double a[], int n) {
    /* a je pole koeficientov polynómu s n hodnotami */
    for (int i = 0; i < n; i++) {
        cout << "Koeficient polynomu pri x na " << i << " je " << a[i] << endl;
    }
}

void testEvaluate() {
    int n;
    double a[maxN];

    enterPolynomial(a, n, maxN);
    double x;
    cout << "Zadaj x: ";
    cin >> x;
    cout << "Hodnota pre x=" << x << " je " << evaluatePolynomialPow(a, n, x) << endl;
    cout << "Hodnota pre x=" << x << " je " << evaluatePolynomialMult(a, n, x) << endl;
    cout << "Hodnota pre x=" << x << " je " << evaluatePolynomialHorner(a, n, x) << endl;
}

void testAdd() {
    int na, nb;
    double a[maxN], b[maxN];
    cout << "Prvy polynom:" << endl;
    enterPolynomial(a, na, maxN);
    cout << endl << "Druhy polynom:" << endl;
    enterPolynomial(b, nb, maxN);
    double c[maxN];
    int nc;
    addPolynomials(a, na, b, nb, c, nc);
    cout << endl << "Ich sucet:" << endl;
    writePolynomial(c, nc);
}

int main(void) {

    testEvaluate();
    testAdd();

}

Zdrojový kód programu s triedeniami

/* Program s triedeniami z prednášky 6.
   http://compbio.fmph.uniba.sk/vyuka/prog/index.php/Predn%C3%A1%C5%A1ka_6 */
#include <iostream>
using namespace std;

void swap(int &x, int &y) {
    /* Vymeň hodnoty premenných x a y. */
    int tmp = x;
    x = y;
    y = tmp;
}

void printArray(int a[], int n) {
   for (int i = 0; i < n; i++) {
       cout << " " << a[i];
   }
   cout << endl;
}

void bubbleSort(int a[], int n) {
    /* usporiadaj prvky v poli a od najmenšieho po najväčší */

    bool hotovo = false;
    while (!hotovo) {
        bool vymenil = false;
        /* porovnávaj všetky dvojice susedov, vymeň ak menší za väčším */
        for (int i = 1; i < n; i++) {
            if (a[i] < a[i - 1]) {
                swap(a[i - 1], a[i]);
                vymenil = true;
            }
        }
        /* ak sme žiadnu dvojicu nevymenili, môžeme skončiť. */
        if (!vymenil) {
            hotovo = true;
        }
    }
}
int maxIndex(int a[], int n) {
    /* vráť index, na ktorom je najväčší prvok z prvkov a[0]...a[n-1] */
    int index = 0;
    for(int i=1; i<n; i++) {
        if(a[i]>a[index]) {
            index = i;
        }
        /* invariant: a[j]<=a[index] pre vsetky j=0,...,i*/
    }
    return index;
}

void selectionSort(int a[], int n) {
    /* usporiadaj prvky v poli a od najmenšieho po najväčší */

    for(int kam=n-1; kam>=1; kam--) {
        /* invariant: a[kam+1]...a[n-1] sú utriedené
         * a pre každé i,j také že 0<=i<=kam, kam<j<n platí a[i]<=a[j] */
        int index = maxIndex(a, kam+1);
        swap(a[index], a[kam]);
    }
}

void insertionSort(int a[], int n) {
    /* usporiadaj prvky v poli a od najmenšieho po najväčší */

    for (int i = 1; i < n; i++) {
        // inv1
        int prvok = a[i];
        int kam = i;
        while (kam > 0 && a[kam - 1] > prvok) {
            // inv2
            a[kam] = a[kam - 1];
            kam--;
        }
        a[kam] = prvok;
    }
}

int main(void) {
    int n = 6;
    int a[6] = {9, 3, 7, 4, 5, 2};

    printArray(a, n);
    insertionSort(a, n);
    printArray(a,n);
}