Quick_Sort

/*
    Was it all worth it ??
    In the end all it remains are just memories!!!

*/

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

#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ld long double
#define pb push_back
#define fe first
#define se second
#define nl "\n"
#define pp pair < ll , ll >
#define sz(x) (ll)x.size()
#define st(x) sort(x.begin(),x.end())
#define rst(x) sort(x.rbegin(), x.rend())
#define all(x) x.begin(),x.end()
long double pi = 3.14159265358979323;

const double EPS = 1e-12;
const int N = 1e6 + 5;
//Just A Gentle Reminder about MOD
const int mod = 1e9 + 7;

//Quick Sort

void print(ll n , ll arr[]){
    for(int i = 0 ; i < n ; i++ )cout << arr[i] << " ";
}
ll partiton(ll arr[] , ll low , ll high){
        int i = low - 1;
        ll pivot = arr[high];
        for(int j = low ; j <= high ; j++ ){
                if(arr[j] < pivot){
                    i++ ;
                    swap(arr[j] , arr[i]);
                }
        }
        swap(arr[i+1] , arr[high]);
        return (i+1);
}

void Quick_Sort(ll arr[] , ll low , ll high){

        if(low < high){
            int pi = partiton(arr , low , high);
            Quick_Sort(arr , low , pi - 1);
            Quick_Sort(arr , pi + 1 , high);
        }
        //Best Case - O(nlogn)
        //Worst cas - O(n^2) - when array is already sorted
        //Memory - Stack Memory O(logn)
}



int main()
{
    fast;
    ll n;
    cin >> n ;
    ll arr[n];
    for(int i = 0 ; i < n ;i++ ){
        cin >> arr[i];
    }

    Quick_Sort(arr , 0 , n - 1);
    cout << "Quick_Sort\n";
    print(n , arr);






















    return 0;
//It's not end it yet
}