quick_sort_using_recursion.cpp

#include<iostream>
#include<vector>
using namespace std;

int partition(int arr[], int s, int e){
    int pivot=arr[s];

    //Count elements smaller than pivot
    int cnt=0;
    for(int i=s+1; i<=e; i++){
        if(arr[i]<=pivot){
            cnt++;
        }
    }

    //Placing pivot element at right position
    int pivotIndex=s+cnt;
    swap(arr[pivotIndex],arr[s]);

    //Putting elements smaller than pivot to left and greater than pivot to right
    int i=s, j=e;
    while(i<pivotIndex && j>pivotIndex){
        while(arr[i]<=pivot){
            i++;
        }
        while(arr[j]> pivot){
            j--;
        }
        if(i<pivotIndex && j>pivotIndex){
            swap(arr[i++],arr[j--]);
        }
    }
    return pivotIndex;
}

void quickSort(int arr[], int s, int e){

    //Base case
    if(s>=e)
        return;
    
    //Partition
    int p=partition(arr,s,e);

    //Sort left part
    quickSort(arr,s,p-1);

    //Sort right part
    quickSort(arr,p+1,e);
}

int main(){
    int arr[5]={4,6,2,7,1};
    int n=5;

    quickSort(arr,0,n-1);

    for(int i=0; i<n; i++){
        cout<<arr[i]<<" ";
    }

    return 0;
}