======= Quicksort ======

http://gitlab.fjfi.cvut.cz/culikzde/zalg/-/blob/master/quicksort/quicksort.cpp

===== Funkce quicksort (int r, int s) =====

Funkce **quicksort** sparametry **(r, s)** má setřídit část globálního pole **a**. \\
Třídí prvky **a[r]**, ..., **a[s]**. \\

==== Výběr pivotu ====

Vybereme si jednu hodnotu z této části, nazveme ji //pivot// a uložíme do proměnné **h**.

<code C++>
    h = a [ (r+s)/2 ]; 
</code>

:?: Tuto značku budu používat pro poznámky, které se napoprvé nezdají důležité, ale jsou významné pro správně fungující program. \\
:?: **int / int** ... celočíselné dělení, pro nezáporné parametry zaokrouhluje dolu \\
:?: výraz **(r+s)/2** je větší nebo roven **r** a menší nebo roven **s** \\
:?: hodnota **h** se skutečně nalézá někde v posloupnosti **a[r]**, ..., **a[s]** 

<code>
   r                                              s
   .----------------------------------------------.
   |                    | h |                     |
   .----------------------------------------------.
</code>



==== Rozdělení na tři části ====

Posloupnost **a[r]**, ..., **a[s]** chceme rozdělit na tři části (krajní mohou být prázdné).

<code>
   .---------------------------------------------------.
   |    a[t] <= h    |    a[t] = h   |    a[t] >= h    |
   .---------------------------------------------------.
</code>

:?: Hodnoty **h** mohou být umístěny do libovolné části. \\


==== Postupujeme zdola a shora ====

Zavedeme dvě proměnné **i** a **k**. \\
Do proměnné **i** uložíme index levého okraje **r** a budeme ji postupně **zvětšovat**. \\
Do proměnné **k** uložíme index pravého okraje **s** a budeme ji postupně **zmenšovat**. \\

<code C++>
    int i = r;
    int k = s;
 
    while (i <= k)
    {
       /* ... */
    }
</code>

<code>
   r                                              s
   .----------------------------------------------.
   |                    | h |                     |
   .----------------------------------------------.
         i --->                         <--- k
</code>

Pokud uvnitř **while** cyklu potkáme hodnoty **ostře menší** než **h**, proměnnou **i** zvětšíme. \\
Pokud potkáme hodnoty **ostře větší** než **h**, proměnnou **k** zmenšíme. 

:?: V definici krajních oblastí máme **"< ="** a **"> ="**, ale zde používáme **"<"** a **">"**. \\
Máme jistou, že hodnota **h** je někde uprostřed a funguje jako zarážka.

<code C++>
    while(i <= k)
    {
        while (a[i] < h) i++;
        while (a[k] > h) k--;
        /* ... */
    }

</code>

**i** a **k** tedy přeskočí ostře menší a ostře větší hodnoty. \\
hodnoty rovné **h** nepřeskakujeme, ponecháme si je jako zarážku.

<code>
   r                                                                  s
   .------------------------------------------------------------------.
   |    a[ ] <= h     |     zde se někde nalézá h   |    a[ ] >= h    |
   .------------------------------------------------------------------.
                       i --->                 <--- k
</code>

:?: Prohozenou hodnotu //"házíme před sebe ve směru pohybujícího se indexu"//. \\
Prohozená hodnota bude //"zarážkou"// pro příští průchody cyklem.


==== Prohození hodnot ====

Po provedení menších **while** cyklů je situace následující:

<code>
   r                            i                              k                           s
   .---------------------------------------------------------------------------------------.
   |    a[ ] <= h         | a[i] >= h |                  | a[k] <= h |        a[ ] >= h    |
   .---------------------------------------------------------------------------------------.
</code>

Po skončení obou menších **while** cyklů musí platit obrácené podmínky cyklů ** a[i] > = h **  ,  ** a[k] < = h **.

Pokud stále platí **i < = k**, hodnoty **a[i]** a **a[k]** prohodíme. \\
Indexy **i** a **k** zvětšíme a zmenšíme. \\
:?: Zde se nám hodí definice krajních oblastí s neostrou nerovností

<code C++>
        if (i <= k)
        {
            swap (a[i], a[k]);
            i++;
            k--;
        }
</code>

Situace po prohození:

<code>
   r                                   i                k                                  s
   .---------------------------------------------------------------------------------------.
   |    a[ ] <= h                     |                  |                    a[ ] >= h    |
   .---------------------------------------------------------------------------------------.
</code>


==== Cyklus opakujeme, dokud se indexy nepřekříží ====

Pokud nyní **i < = k**, opakujeme vnější **while** cyklus.

<code C++>

    while (i <= k)
    {
        while (a[i] < h) i++;
        while (a[k] > h) k--;

        if (i <= k)
        {
            swap (a[i], a[k]);
            i ++;
            k --;
        }
    }
</code>

:?: Pokud i = k, nemusím nic prohazovat, ale zvětšit a zmenšit indexy je **nezbytné** (jinak se program dostane do nekonečného cyklu)


==== Až cyklus skončí, rekuzivně zpracujeme okraje ====

Po skončení **while** cyklu \\
index **i** //"přeběhl"// do pravé oblasti, \\
index **k** //"přeběhl"// do levé oblasti.

Levá oblast je tvořena prvky **a[r]**, ..., **a[k]**. \\
Pravá oblast je tvořena prvky **a[i]**, ..., **a[s]**. \\

<code>
    r                       k                          i                     s
   .---------------------------------------------------------------------------.
   |        a[ ] <= h        |        a[ ] = h        |        a[ ] >= h       |
   .---------------------------------------------------------------------------.
</code>

Prostřední oblast obsahuje samé hodnoty **h**, už ji nemusíme třídit. \\
Levou část (pokud není **prázdná** nebo **jednoprvková**) setřídíme rekurzivním voláním funkce **quicksort (r, k)**. \\
Obdobně oravou část setřídíme rekurzivním voláním funkce **quicksort (i, s)**. \\


<code C++>
    if (r < k) quicksort (r, k);
    if (i < s) quicksort (i, s);
</code>

:?:  Kontroly **r < k**  a **i < s** zabrání nekonečné rekurzi



==== Celá funkce quicksort ====

<code C++>
void quicksort (int r, int s)
{
    int h = a [(r + s) / 2];    // r <= (r+s)/2 <= s
    int i = r;
    int k = s;

    while (i <= k)
    {
        while (a[i] < h) i++;
        while (a[k] > h) k--;

        if (i <= k)
        {
            swap(a[i], a[k]);
            i++;
            k--;
        }
    }

    if (r < k) quicksort (r, k);
    if (i < s) quicksort (i, s);
}
</code>



===== Celý program =====

Vygenerujeme pseudonáhodné hodnoty, spustíme **funkci quicksort (0, N-1)**, vytiskneme a zkontrolujeme.

<code C++>
#include <iostream>
#include <stdlib.h> /* srand, rand */
#include <time.h>   /* time */
using namespace std;

const int N = 1000;
// const int N = 1000000;

int a [N];

inline void swap (int & a, int & b)
{
    int t = a;
    a = b;
    b = t;
}

void quicksort (int r, int s)
{
    int h = a [(r + s) / 2];    // r <= (r+s)/2 <= s
    int i = r;
    int k = s;

    while (i <= k)
    {
        while (a[i] < h) i++;
        while (a[k] > h) k--;

        if (i <= k)
        {
            swap (a[i], a[k]);
            i++;
            k--;
        }
    }

    if (r < k) quicksort (r, k);
    if (i < s) quicksort (i, s);
}

int main()
{
    srand (time (NULL));

    for (int i = 0; i < N; i++)
        a[i] = rand() % 50000;

    quicksort (0, N-1);

    bool ok = true;
    for (int i = 0; i < N; i++)
    {
        cout << a[i];
        if (i < N - 1 && a[i] > a[i + 1]) { ok = false; cout << " CHYBA"; }
        cout << endl;
    }
    if (ok)  cout << "O.K." << endl;
}
</code>


===== Složitost =====

:!: Pocet instrukcí while cyklu ve funkci quicksort je úměrný počtu prvků posloupnosti **a[r]**, ..., **a[s]**. \\
V každém volání funkce quicksort ubyde alespoň jeden prvek (s hodnotou **h**) a zbylá dvě volání quicksort mají k zpracování o jeden prvek méně. \\
Tj. n + (n-1) + (n-2) + ... + 1 instrukcí, kde n je počet tříděných prvků v celém poli. \\
V nejhorším případě je složitost ** O (n^2) 

:!: Průměrná složitost je O (n log n), viz skripta konec kapitoly 5.1.7