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 10

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

Oznamy

  • DÚ5 odovzdávajte do pondelka 24.10. 22:00.
  • Budúci týždeň 24.10.-29.10.:
    • utorok prednáška rekurzia, cvičenie
    • streda opakovacia prednáška - cykly, rekurzia
    • doplnkové cvičenia nebudú
  • Ďalší týždeň 30.10.-6.11.:
    • utorok je sviatok, prednáška aj cvičenia nebudú
    • zvyšok týždňa (prednáška, doplnkové cvičenie) podľa rozvrhu

Opakovanie rekurzie

Kochova krivka stupňa 3
  • Rekurentná definícia: určitý objekt definujeme pomocou menších objektov toho istého typu
    • Napr. Fibonacciho čísla F(n) = F(n-1) + F(n-2)
    • Napr. fraktál stupňa n ako kompozícia fraktálov stupňa n-1
    • Nezabudnime na triviálne prípady, napr. F(0)=F(1)=1, fraktál stupňa 0
  • Rekurentné definície vieme často priamočiaro zapísať do rekurzívnych funkcií (aj keď môžu byť pomalé)
int fib(int n) {
    if (n<2) return 1;
    else return fib(n-1) + fib(n-2);
}
  • V rekurzívnej funkcii riešime problém pomocou menších podproblémov toho istého typu
    • Napríklad aby sme našli číslo x v utriedenom poli medzi indexami left a right, potrebujeme ho porovnať so stredným prvkom tohoto intervalu a potom riešiť tú istú úlohu pre menší interval
    • Aj keď sme pôvodne chceli hľadať prvok v celom poli, úlohu rozšírime o parametre left a right, aby sa dala spraviť rekurzia
bool contains (int a[], int left, int right, int x){
    if (left == right) return (a[left] == x);
    int index = (left + right) / 2;
    if (x <= a[index]) return contains(a, left, index, x);
    else return contains(a, index+1, right, x);
}
  • Druhý pohľad na rekurziu je dynamický: môžeme simulovať, čo sa v programe deje so zásobníkom
    • Na zásobníku ukladáme parametre, lokálne premenné a miesto, kde v kóde sme skončili
    • Skúsme napríklad odsimulovať, čo sa deje ak vo funkcii main zavoláme fib(3)
    • Kvôli prehľadnosti si fib rozpíšeme na viac riadkov:
#include <iostream>
using namespace std;

int fib(int n) {
    if (n < 2) return 1;
    else {
        int a = fib(n - 1); // riadok (A)
        int b = fib(n - 2); // riadok (B)
        return a+b;
    }
}

int main(void) {
    int x = fib(3);    // riadok (C)
    cout << x << endl; 
}

Tu je priebeh programu (obsah zásobníka)

(1)          (2)                      (3)

                                       fib n=2
              fib n=3                  fib n=3, a=?, b=?, riadok A
main, x=?     main, x=?, riadok C      main, x=?, riadok C

(4)                             (5)
 
fib n=1                         
fib n=2, a=?, b=?, riadok A     fib n=2, a=1, b=?, riadok A
fib n=3, a=?, b=?, riadok A     fib n=3, a=?, b=?, riadok A
main, x=?, riadok C             main, x=?, riadok C             


(6)                             (7)
 
fib n=0                         
fib n=2, a=1, b=?, riadok B     fib n=2, a=1, b=1, riadok B
fib n=3, a=?, b=?, riadok A     fib n=3, a=?, b=?, riadok A
main, x=?, riadok C             main, x=?, riadok C             


(8)                             (9)

                                fib n=1
fib n=3, a=2, b=?, riadok A     fib n=3, a=2, b=?, riadok B 
main, x=?, riadok C             main, x=?, riadok C                 


(10)                            (11)

fib n=3, a=2, b=1, riadok B     
main, x=?, riadok C             main, x=3, riadok C 

Efektívnejší výpočet Fibonacciho čísel

Priamočiary rekurzívny zápis výpočtu Fibonacciho čísel je neefektívny, lebo výpočet Fibonacciho čísel sa opakuje

  • Napr. pre n=4 počítame fib(2) dvakrát, pre n=6 päťkrát a pre n=20 až 4181-krát

Spomeňme si na zápis výpočtu bez rekurzie, s dvomi premennými:

  • F(n) spočíta v čase O(n)
int fibonacci(int n) {

    int f = 1;     // Cislo F(i) 
    int oldF = 0; // Cislo F(i-1)
    
    for (int i = 2; i <= n; i++) {
        int newF = f + oldF;  // spocitaj nove F(i) pre vyssie i
        oldF = f;             // poposuvaj hodnoty
        f = newF;
    }

    return f;
}

Prepíšeme ho na rekurziu:

int fib1(int a, int b, int i, int n) {
    /* a je F(i-1), b je F(i), spočítaj F(n), kde n>=i */
    if (n == i) return b;
    else return fib1(b, a+b, i+1, n);
}

int fib(int n){
    return fib1(1, 1, 1, n);
}

Namiesto dvoch premenných i a n si môžeme pamätať len ich rozdiel k=n-i

  • hodnota k nám vraví, koľkokrát máme ešte sčitovať dve posledné čísla
int fib1(int a, int b, int k) {
    /* a je F(i-1), b je F(i), spočítaj F(i+k) */
    if (k == 0) return b;
    else return fib1(b, a+b, k-1);
}

int fib(int n){
    fib1(1, 1, n-1);
}

Táto rekurzívna funkcia pracuje v čase O(n), rovnako ako verzia s cyklom.

Rozdeľuj a panuj, rýchle triedenia

Videli sme tri algoritmy na triedenie: bubblesort, insertsort, maxsort

  • Jednoduché, ale pomalé, kvadratická zložitosť O(n^{2})

Dnes si ukážeme dve rýchlejšie triedenia, mergesort a quicksort.

  • obe používajú metódu rozdeľuj a panuj

Rozdeľuj a panuj je všeobecný rekurzívny postup, ktorým sa dá riešiť viacero problémov. Má nasledujúce fázy:

  • Rozdeľuj: rozdelíme problém na nejaké menšie časti (podproblémy), ktoré sa dajú riešiť ďalej samostatne.
  • Vyriešime podproblémy: rekurzívne vyriešime úlohu pre každý podproblém
  • Panuj: spojíme výsledky pre podproblémy do výsledku celkového problému.

Triedenie zlučovaním, MergeSort

V triedení zlučovaním sa pole veľkosti N rozdelí na polovicu najjednoduchším spôsobom - na prvú a druhú polovicu. Tieto rekurzívne utriedime, čím dostávame 2 utriedené postupnosti. Preto vo fáze panuj potrebujeme tieto dve polia zlúčiť (merge) do výsledného poľa.

void mergesort(int a[], int low, int high) {
/* utriedi prvky pola a od indexu low po index high (vratane) */

 
    // trivialny pripad: ak mame 1 alebo 0 prvkov
    if (low >= high) return;

    // rozdeluj: spocita stred triedeneho useku
    int mid = (low+high) / 2;

    //rekurzivne volanie na dva podproblemy
    mergesort(a, low, mid);       // triedi prvky od low po mid
    mergesort(a, mid+1, high);    // triedi prvky od mid+1 po high 

    // panuj: zluci dve utriedene postupnosti do jednej 
    merge(a, low, mid, high);
}

Zlučovanie utriedených postupností

Zostáva nám naprogramovať zlúčenie dvoch utriedených postupností. V prvej verzii predpokladajme, že máme dve utriedené postupnosti A[0..N-1] a B[0..M-1] a chceme ich zlúčiť do utriedeného poľa C dĺžky N+M.

  • Prvým prvkom výslednej postupnosti bude menší z prvkov A[0] a B[0]. Potom ostávajú postupnosti A[1..N-1] a B[0..M-1] alebo A[0..N-1] a B[1..M-1].
  • Vo všeobecnosti máme postupnosti A[i..N-1] a B[j..M-1]. Ďalším prvkom postupnosti bude buď A[i] alebo B[j] a ostanú nám postupnosti A[i+1..N-1] a B[j..M-1] alebo A[i..N-1] a B[j+1..M-1].
  • Toto robíme dovtedy, kým s jedným poľom neskončíme. Vtedy na koniec dokopírujeme zvyšok druhého poľa.

Z toho dostávame nasledovnú funkciu.

void merge(int A[], int N, int B[], int M, int C[]) {
    /* zluci utriedene pole A dlzky N a utriedene pole B dlzky M 
     * do pola C, ktore musi mat dlzku aspon N+M */

    int i = 0;
    int j = 0;
    while (i < N && j < M) { // kym v oboch poliach zostavaju prvky
        if (A[i] <= B[j]) {
            C[i + j] = A[i]; // vysledok ukladame na (i+j)-te miesto
            i++;
        } else {
            C[i + j] = B[j];
            j++;
        }
    }

    while (i < N) { // ak skoncilo pole B, prekopirujeme zvysok pola A
        C[i + j] = A[i];
        i++;
    }

    while (j < M) {  // ak skoncilo pole A, prekopirujeme zvysok pola B
        C[i + j] = B[j];
        j++;
    }
}

Výsledný MergeSort

Ostáva už iba drobnosť: nezlučujeme dve nezávislé polia, ale prvky jedného poľa a navyše by sme radi, aby tie prvky v tomto poli aj skončili.

  • Funkcia namiesto dvoch vstupných polí dostane iba pole A a pozície začiatkov a koncov úsekov.
    • Keďže zlučované úseky idú za sebou, stačia nám tri indexy: low, mid a high
    • Hodnotu mid by sme si mohli aj dopočítať z low a high.
  • Druhý problém vyriešime pomocným poľom C, ktoré na konci nakopírujeme naspäť do A.
    • Keďže merge už nevolá ďalšie funkcie, v zásobníku bude vždy len jedno pole C, po skončení zlučovania sa vždy vymaže.
#include <iostream>
using namespace std;

const int MAX = 100;

void merge(int A[], int low, int mid, int high) {
    /* V poli A su utriedene useky A[low..mid] a A[mid+1..high.
     * Zluci ich do utriedeneho useku A[low..high]. */

    int C[MAX];       // pomocne pole
    int i = low;      // poloha v prvej catsi pola
    int j = mid + 1;  // poloha v druhej casti pola
    int k = 0;        // poloha v zlucenom poli
    while (i <= mid && j <= high) { // kym v oboch poliach zostavaju prvky
        if (A[i] <= A[j]) {  // pouzi prvok z lavej casti
            C[k] = A[i];
            i++;
            k++;
        } else {            // pouzi prvok z pravej casti
            C[k] = A[j];
            j++;
            k++;
        }
    }

    while (i <= mid) { // ak skoncila prava cast, prekopirujeme zvysok lavej
        C[k] = A[i];
        i++;
        k++;
    }

    while (j <= high) { // ak skoncila lava cast, prekoprujeme zvysok pravej
        C[k] = A[j];
        j++;
        k++;
    }

    for (int k = low; k <= high; k++) {
        A[k] = C[k - low];
    }
}

void mergesort(int A[], int low, int high) {
    /* utriedi prvky pola a od indexu low po index high (vratane) */

    // trivialny pripad: ak mame 1 alebo 0 prvkov
    if (low >= high) return;

    // rozdeluj: spocita stred triedeneho useku
    int mid = (low + high) / 2;

    //rekurzivne volanie na dva podproblemy
    mergesort(A, low, mid);
    mergesort(A, mid + 1, high);

    // panuj: zluci dve utriedene postupnosti do jednej
    merge(A, low, mid, high);
}

int main(void) {
    const int N = 10;
    int A[N] = {13, 1, 5, 7, 2, 4, 8, 10, 3, 24};
    mergesort(A, 0, N - 1);
    for (int i = 0; i < N; i++) cout << A[i] << " ";
}

Ukážka na príklade

Pole A[]= {6, 1, 5, 7, 2, 4, 8, 9, 3, 0};

Všetky volania:

sort(0,9) sort(0,4) sort(0,2) sort(0,1) sort(0,0) 
          .         .         .         sort(1,1)
          .         .         .         merge(0,0,1)
          .         .         sort(2,2)
          .         .         merge(0,1,2)
          .         sort(3,4) sort(3,3)
          .         .         sort(4,4)
          .         .         merge(3,3,4)
          .         merge(0,2,4)
          sort(5,9) sort(5,7) sort(5,6) sort(5,5)
          .         .         .         sort(6,6)
          .         .         .         merge(5,5,6)
          .         .         sort(7,7)
          .         .         merge(5,6,7)
          .         sort(8,9) sort(8,8)
          .         .         sort(9,9)
          .         .         merge(8,8,9)
          .         merge(5,7,9)
          merge(0,4,9)

Čo sa deje v poli:

merge(A,0,0,1): |6|1|5 7 2 4 8 9 3 0 -> |1 6|5 7 2 4 8 9 3 0
merge(A,0,1,2): |1 6|5|7 2 4 8 9 3 0 -> |1 5 6|7 2 4 8 9 3 0
merge(A,3,3,4):  1 5 6|7|2|4 8 9 3 0 ->  1 5 6|2 7|4 8 9 3 0
merge(A,0,2,4): |1 5 6|2 7|4 8 9 3 0 -> |1 2 5 6 7|4 8 9 3 0
merge(A,5,5,6):  1 2 5 6 7|4|8|9 3 0 ->  1 2 5 6 7|4 8|9 3 0
merge(A,5,6,7):  1 2 5 6 7|4 8|9|3 0 ->  1 2 5 6 7|4 8 9|3 0
merge(A,8,8,9):  1 2 5 6 7 4 8 9|3|0|->  1 2 5 6 7 4 8 9|0 3|
merge(A,5,7,9):  1 2 5 6 7|4 8 9|0 3|->  1 2 5 6 7|0 3 4 8 9|
merge(A,0,4,9): |1 2 5 6 7|0 3 4 8 9|-> |0 1 2 3 4 5 6 7 8 9|

Odhad zložitosti

Zlučovanie dvoch postupností, ktoré spolu obsahujú N prvkov, trvá čas O(N). Prečo?

V algoritme máme \log _{2}N úrovní rekurzie, lebo na prvej spracovávame úseky dĺžky N, na druhej N/2 na tretej N/4 atď, až pol \log _{2}N úrovniach dostaneme úseky dĺžky 1. Na každej úrovni je každý prvok najviac v jednom zlučovaní, teda celkový čas zlučovaní na každej úrovni je O(N). Celkový čas výpočtu je O(N log N).

Quicksort

Quicksort je tiež založený na metóde rozdeľuj a panuj. Postupuje nasledovne:

  • Rozdeľuj: prvky poľa rozdelí na dve skupiny: prvky menšie ako nejaké x a prvky väčšie alebo rovné x
    • hodnotu x nazývame pivot
  • Rekurzívne utriedi obe skupiny prvkov a dostáva dve utriedené postupnosti - utriedenú postupnosť menších prvkov a utriedenú postupnosť väčších prvkov.
  • Panuj: stačí dať tieto utriedené postupnosti za seba (najskôr menšie, potom väčšie)
void quicksort(int A[], int low, int high) {
    /* utriedi prvky v A medzi low a high (vratane) */
    
    if (low >= high) return;  // trivialny pripad: 0 alebo 1 prvok

    // rozdelenie: mid je posledny index medzi mensimi prvkami
    int mid = partition(A, low, high);

    quicksort(A, low, mid);     // rekurzivne utried mensie prvky
    quicksort(A, mid + 1, high); // rekurzivne utried vacsie prvky

    //zlucenie nebude treba - su spravne za sebou
}

Čo sa stane, ak funkcia partition zvolí taký pivot, že jedna zo skupín je prázdna?

Aby sme sa takýmto problémom vyhli, upresníme trochu úlohu funkcie partition:

  • ako pivot x si zvolí jeden z prvkov A[low..high]
  • preusporiada túto časť poľa tak, že
    • A[low..mid-1] obsahuje prvky < x
    • A[mid+1..high] onsahuje prvky >= x
    • A[mid] obsahuje x, ktorý je teda už na svojom finálnom mieste
  • vráti index mid

Potom stačí rekurziu volať na A[low..mid-1] a A[mid+1..high]

Ak sme teda začali s N prvkami, ľavá aj pravá časť poľa bude mať najviac N-1 prvkov.

Rozdelenie prvkov, funkcia partition

Jednoduchá implementácia funkcie partition by mohla používať dve pomocné polia: do jedného si dá menšie prvky, do druhého väčšie.

Dá sa však ľahko napísať priamo v poli A, bez pomocných polí. Počas algoritmu budeme udržiavať nasledujúci invariant:

  • na indexe low je pivot x
  • na indexoch low+1..lastLeft sú prvky menšie ako x
  • na indexoch lastLeft+1..unknown-1 sú prvky >= x
  • na indexoch unknown..high sú prvky, ktoré sme ešte s x neporovnali

V každom kroku porovnáme A[unknown] s x

  • ak je menší, potrebujeme ho dať do ľavej časti, vymeníme ho teda s A[lastLeft+1] a rozšírime ľavú časť
  • ak je >= x, jednoducho rozšírime pravú časť

Nakoniec ešte vymeníme A[low] a A[lastLeft], čím sa pivot dostane na svoje miesto

int partition(int A[], int low, int high) {
    /* vrati index mid (low<=mid<=high)
     * a preusporiada prvky v a[low..high] tak, ze plati
     * A[low..mid-1] obsahuje prvky < A[mid]
     * A[mid+1..high] obsahuje prvky >= A[mid] */

    // ak chceme pouzit iny prvok ako pivot, vymenime ho s a[low]
    int pivot = A[low];
    int lastLeft = low;
    for (int unknown = low + 1; unknown <= high; unknown++) {
        if (A[unknown] < pivot) {
            lastLeft++;
            swap(A[unknown], A[lastLeft]);
        }
    }
    swap(A[low], A[lastLeft]);
    return lastLeft;
}

Výsledný Quicksort

#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;
}

int partition(int A[], int low, int high) {
    /* vrati index mid (low<=mid<=high)
     * a preusporiada prvky v a[low..high] tak, ze plati
     * A[low..mid-1] obsahuje prvky < A[mid]
     * A[mid+1..high] obsahuje prvky >= A[mid] */

    // ak chceme pouzit iny prvok ako pivot, vymenime ho s a[low]
    int pivot = A[low];
    int lastLeft = low;
    for (int unknown = low + 1; unknown <= high; unknown++) {
        if (A[unknown] < pivot) {
            lastLeft++;
            swap(A[unknown], A[lastLeft]);
        }
    }
    swap(A[low], A[lastLeft]);
    return lastLeft;
}

void quicksort(int A[], int low, int high) {
    /* utriedi prvky v A medzi low a high (vratane) */
    
    if (low >= high) return;  // trivialny pripad: 0 alebo 1 prvok

    // rozdelenie: mid je posledny index medzi mensimi prvkami
    int mid = partition(A, low, high);

    quicksort(A, low, mid - 1);     // rekurzivne utried mensie prvky
    quicksort(A, mid + 1, high); // rekurzivne utried vacsie prvky
}

int main(void) {
    const int N = 10;

    int A[N] = {6, 1, 5, 7, 2, 4, 8, 9, 3, 0};
    quicksort(A, 0, N - 1);
    for (int i = 0; i < N; i++) cout << A[i] << " ";
}

Príklad

Volania funkcií

sort(0,9) sort(0,5) sort(0,-1)
          .         sort(1,5) sort(1,0)
          .         .         sort(2,5) sort(2,4) sort(2,2)
          .         .         .         .         sort(4,4)
          .         .         .         sort(6,5)
          sort(7,9) sort(7,8) sort(7,7)
                    .         sort(9,8)
                    sort(10,9)

Čo robí partition:

partition(0,9): |6 1 5 7 2 4 8 9 3 0| -> |0 1 5 2 4 3|6|9 7 8|
partition(0,5): |0 1 5 2 4 3|6 9 7 8  -> |0|1 5 2 4 3|6 9 7 8
partition(1,5):  0|1 5 2 4 3|6 9 7 8  ->  0|1|5 2 4 3|6 9 7 8
partition(2,5):  0 1|5 2 4 3|6 9 7 8  ->  0 1|3 2 4|5|6 9 7 8
partition(2,4):  0 1|3 2 4|5 6 9 7 8  ->  0 1|2|3|4|5 6 9 7 8
partition(7,9):  0 1 2 3 4 5 6|9 7 8| ->  0 1 2 3 4 5 6|8 7|9|
partition(7,8):  0 1 2 3 4 5 6|8 7|9  ->  0 1 2 3 4 5 6|7|8|9

Cvičenie:

  • Ako sa bude Quicksort správať, keď mu dáme utriedené pole?
  • Ako sa bude správať, ak budú prvky v poli od najväčšieho po najmenšie?

Odhad zložitosti

V ideálnom prípade pivot rozdelí pole na dve rovnako veľké časti. Vtedy je čas výpočtu O(N log N), podobne ako pre Mergesort.

Nepríjemné je, keď pivot je vždy najmenší alebo najväčší prvk v danom úseku. Vtedy je čas O(N^{2}). Dobrá správa je, že takýchto prípadov nie je príliš veľa.

  • Aby sme sa vyhli problémom, ak je vstupné pole (takmer) utriedené, môžeme ho pred triedením náhodne premiešať alebo vyberať ako pivot náhodný prvok z intervalu

Iná implementácia

Občas sa môžete stretnúť aj s takto napísaným quicksortom. Skúste si premyslieť, prečo funguje a prečo si môžeme dovoliť niektoré prvky vynechať.

void quickSort(int A[], int left, int right) {
    if (left>=right) return;
    int i = left, j = right;
    int pivot = A[(left + right) / 2];

    /* partition */
    while (i <= j) {
        while (A[i] < pivot) i++;
        while (A[j] > pivot) j--;
        if (i <= j) {
            int tmp = A[i]; A[i] = A[j]; A[j] = tmp;
            i++; j--;
        }
    };

    /* rekurzia */
    quickSort(A, left, j);
    quickSort(A, i, right);
}

Zhrnutie: triedenia

Jednoduché triedenia: bubblesort, insertsort, maxsort

  • Jednoduché, ale pomalé, zložitosť O(n^{2})

Rekurzívne triedenia, rozdeľuj a panuj

  • Rýchlejšie, zložitejšie
  • Mergesort, zložitosť O(n\log n)
  • Quicksort, zložitosť O(n^{2}) v najhoršom prípade, pre väčšinu stupov O(n\log n), väčšinou rýchlejší ako Mergesort

Príklad: na mojom počítači som triedila pol milióna náhodne permutovaných čísel programami z prednášok

  • quicksort: 0.25s
  • mergesort: 0.27s
  • insertionsort: 58s

Medián

Medián prvkov v poli je prvok, ktorý by po utriedení bol v strede poľa.

  • Pre N prvkové pole je teda (N/2)-ty najmenší prvok.

Jednoduchý algoritmus: utriedime pole, vypíšeme A[N/2].

  • Zložitosť O(n^{2}) alebo O(n\log n) podľa použitého triedenia

Ukážeme si rýchlejší algoritmus, O(n^{2}) v najhoršom prípade, väčšina vstupov O(n)

  • Zovšeobecníme problém: hľadáme prvok, ktorý by bol v utriedenom pole na mieste k (0<=k<n)
  • Podobný na Quicksort, ale niektoré časti nebudeme triediť

Postup:

  • Pole si rozdelíme ako pri quicksorte. Nech prvá časť má m prvkov. Potom
    • ak k<m, stačí nám hľadať k-ty najmenší prvok v prvej časti
    • ak k>m, potrebujeme nájsť (k-m)-tý prvok v druhej časti
int select(int A[], int low, int high, int k) {
    /* vrati prvok, ktory by bol na pozicii low+k, keby sme A[low..high] utriedili */
    assert(0 <= k && k <= high - low);
    if (low == high) return A[low];

    int mid = partition(A, low, high);
    if (k < mid - low) select(A, low, mid - 1, k);
    else if (k > mid - low) select(A, mid + 1, high, k - mid + low - 1);
    else return A[mid];
}