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

12
10 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 <iostream>
#include <algorithm>

using namespace std;
int v[100005];
int asez(int st,int dr)
{
      int i=st-1,c;
      int p=v[dr];
      for(int j=st;j<=dr-1;j++)
      {
            if(v[j]<=p)
            {
                  i++;
                  c=v[i];
                  v[i]=v[j];
                  v[j]=c;
                  //s++;
            }
      }
      c=v[i+1];
      v[i+1]=v[dr];
      v[dr]=c;
      return i+1;
}
void quicksort(int st,int dr)
{
      if(st<dr)
      {
        int n=asez(st,dr);

         quicksort(st,n-1);
         quicksort(n+1,dr);
      }
}
int main()
{
    int n,st=1,dr;
    cin>>n;
    dr=n;
    for(int i=1;i<=n;i++)
    {
          cin>>v[i];
    }
    quicksort(st,dr);
    for(int i=1;i<=n;i++)
    {
          cout<<v[i]<<" ";
    }
    return 0;
}