#include<iostream>

using namespace std;

int __partition(int arr[],int l,int r){
    int v=arr[l];
    int i=l+1;
    int j=l;

    while(i<=r){
        if(arr[i]<v){
            j++;
            swap(arr[i],arr[j]);
            i++;
            
        } else{
            i++;
        }
    }
    swap(arr[l],arr[j]);

    return j;
}

void __quickBasic(int arr[],int l,int r){
    if(l>=r){
        return;
    }
    int p=__partition(arr,l,r);
    __quickBasic(arr,l,p-1);
    __quickBasic(arr,p+1,r);
}

void quickBasic(int arr[],int n){
    __quickBasic(arr,0,n-1);
}

int main(){
    int arr[]={3,2,4,1};
    quickBasic(arr,4);
    for (int i = 0; i < 4; i++)
    {
        cout<<arr[i]<<" ";
    }

    cout<<endl;
    return 0;
}

#include<iostream>

using namespace std;

void __quick2ways(int arr[],int l,int r){
    //arr[l+1...i)<v,arr(j...r]>v
    int i=l+1;
    int j=r;
    int v=arr[l];

    while(i<=j){
        if(i<=r && arr[i]<v){
            i++;
        } 
        else if(j>l+1 && arr[j]>v){
            j--;
        } else{
            //arr[i]>v,arr[j]<v
            swap(arr[i],arr[j]);
            i++;
            j--;
        }
    }

    swap(arr[l],arr[j]);

    
}

void quick2ways(int arr[],int n){
    __quick2ways(arr,0,n-1);
}

int main(){
    int arr[]={3,2,4,1};
    quick2ways(arr,4);
    for (int i = 0; i < 4; i++)
    {
        cout<<arr[i]<<" ";
    }

    cout<<endl;
    return 0;
}

#include<iostream>
#include<algorithm>

using namespace std;

void _quick3ways(int arr[],int l,int r){
    if (l>r)
    {
        return;
    }
    //arr[l+1...lt]<v,arr[lt+1,i)==v,arr[gt...r]>v
    int lt=l;
    int gt=r+1;
    int i=l+1;//next to sort
    int v=arr[l];

    while(i<gt){
        if(arr[i]<v){
            swap(arr[i],arr[lt+1]);
            lt++;
            i++;
        } else if(arr[i]>v){
            swap(arr[i],arr[gt-1]);
            gt--;

        } else{
            i++;
        }
        
    }
    swap(arr[l],arr[lt]);

    _quick3ways(arr,l,lt-1);
    _quick3ways(arr,gt,r);


}

void quick3ways(int a[],int n){
    _quick3ways(a,0,n-1);
}

int main(){
    int arr[]={3,2,4,1};
    quick3ways(arr,4);
    for (int i = 0; i < 4; i++)
    {
        cout<<arr[i]<<" ";
    }

    cout<<endl;
    return 0;
}