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

using namespace std;

int partition(vector<int> &d, int stanga, int dreapta)
{
    int i = stanga, j = dreapta, aux = 0;

    //pivot random 
    int pivot_index = rand() % (dreapta - stanga + 1) + stanga;
    int pivot = d[pivot_index];

    while (i <= j)
    {
        while (d[i] < pivot)
            i++; //pana cand i>=pivot
        while (d[j] > pivot)
            j--; //j<=pivot
        if (i <= j)
        {
            aux = d[i];
            d[i] = d[j];
            d[j] = aux;
            i++;
            j--;
        }
    }

    if (stanga < j)
        partition(d, stanga, j); //apel pe partea cu nr mai mici
    if (i < dreapta)
        partition(d, i, dreapta); // apel pe partea cu nr mai mari
}

void quicksort(vector<int> &d, int stanga, int dreapta)
{
    if (stanga < dreapta)
    {
        partition(d, stanga, dreapta);
    }
}

int main()
{
    ifstream fin("quicksort.in");
    ofstream fout("quicksort.out");

    int n;
    fin >> n;

    vector<int> d(n);

    for (int i = 0; i < n; i++)
        fin >> d[i];

    
    srand(time(0)); // la fiecare rulare un alt pivot 

    quicksort(d, 0, n - 1);

    for (int i = 0; i < n; i++)
        fout << d[i] << " ";

    fin.close();
    fout.close();

    return 0;
}