Cerința

Se dă un șir cu n elemente, numere întregi. Folosind metoda QuickSort (Sortare Rapidă), ordonați crescător elementele acestui șir.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului.

Date de ieșire

Programul va afișa pe ecran elementele șirului sortat, separate prin exact un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• elementele șirului vor fi cuprinse între -1.000.000.000 și 1.000.000.000

Exemplu

Intrare

1210 0 -1 -3 1 -4 9 3 -1 -4 3 -4 

Ieșire

-4 -4 -4 -3 -1 -1 0 1 3 3 9 10

#include <bits/stdc++.h>
using namespace std;

int n, a[100001];

void Quicksort(int st, int dr){
    if(st < dr){
        int mij = (st + dr) / 2;
        swap(a[st], a[mij]);
        int i = st, j = dr, d = 0;
        while(i < j){
            if(a[i] > a[j]){
                swap(a[i], a[j]);
                d = 1 - d;
            }
            i += d;
            j -= 1-d;
        }
        Quicksort(st, i - 1);
        Quicksort(i + 1, dr);
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    Quicksort(1, n);
    for(int i = 1; i <= n; ++i)
        cout << a[i] << ' ';
    return 0;
}