sort_Quick.cpp

/*
   i. Pick a Pivot & place it in its correct place in the sorted array
   ii.smaller in the left ,larger on the Right
*/
#include<bits/stdc++.h>
using namespace std;
int partition(vector<int>& v,int low ,int high)
{
    int pivot=v[low];
    int i=low;
    int j=high;
    while(i<j)
    {
        while(v[i]<=pivot && i<=high-1) i++;
        while(v[j]>pivot && j>=low-1) j--;
        if(i<j) swap(v[i],v[j]);
    }
    swap(v[low],v[j]);
    return j;

}
void quick_sort(vector<int>&v,int low,int high)
{
    if(low<high)
    {
        int pidx=partition(v,low,high);
        quick_sort(v,low,pidx-1);
        quick_sort(v,pidx+1,high);
    }
    return ;
}
int main()
{
    int n;
    cin>>n;
    vector<int>v;
    for(int i=0;i<n;i++)
    {

        int x;
        cin>>x;
        v.push_back(x);
    }
    quick_sort(v,0,n-1);
    for(auto i:v) cout<<i<<" ";

}