#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>

using namespace std;

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

void quick_sort (int *v, int l, int h)
{
    if (l >= h) return;

    int i;
    int pivot;
    int wall; //elements to the left of the wall are smaller than v [pivot]
    int k = l; //k - the current index for v. It increments itself when a value smaller or equal than pivot is found

    srand (time (NULL));
    pivot = rand () % (h - l) + l;

    for (i = l; i <= h; ++ i)
    {
        if (v [i] < v [pivot])
        {
            swap (v [i], v [k]);
            if (k == pivot) pivot = i;
            k ++;
        }
    }
    swap (v [k], v [pivot]);

    wall = k;
    quick_sort (v, l, wall - 1);
    quick_sort (v, wall + 1, h);

}

void print_Array (int *v, int n, ofstream& out)
{
    int i;
    for (i = 0; i < n; ++ i)
        out << v[i] << ' ';
    out << "\n";
}

int main()
{
    ifstream f("algsort.in");
    ofstream g("algsort.out");

    int *v, n, i;
    f >> n;
    v = new int [n];
    for (i = 0; i < n; ++ i)
        f >> v [i];

    quick_sort (v, 0, n - 1);

    print_Array(v, n, g);


    return 0;
}