===== Quick Sort =====

<code C++>
#include <iostream>
#include <time.h>
using namespace std;

// const int N = 7;
// int a [N] = { 10, 4, 8, 20, 7, 5, 1 };

const int N = 1000000;
int a [N];

inline void swap (int i, int k)
{
    int t = a [i];
    a [i] = a [k];
    a [k] = t;
}

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

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

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

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

int main ()
{
    srand (time (nullptr));
    for (int i = 0; i < N; i++)
        a [i] = (rand () % 1000) + 1000 * (rand () % 1000);

    quickSort (0, N-1);

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

    if (ok)
    {
        cout << "O.K." << endl;
    }
}

</code>