Quicksort

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

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

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

    h = a [ (r+s)/2 ];

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]

   r                                              s
   .----------------------------------------------.
   |                    | h |                     |
   .----------------------------------------------.

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

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

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

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.

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

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

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.

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

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.

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

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.

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

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

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í

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

Situace po prohození:

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

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

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

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)

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].

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

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).

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

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

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

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

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

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