#include<stdio.h>

void interchange(int a[],int i,int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

int partition(int a[],int p, int q){
    int v = a[p];
    int i = p,j = q+1;
    do{
        do{
            i = i+1;
        }while(a[i]<v &&  i<=q);
        
        do{
            j = j-1;
        }while(a[j]>v && j>=p);
        
        if(i<j){
            interchange(a,i,j);
        }
    }while(i<j);
    
    interchange(a,p,j);
    return j;
}

void quickSort(int a[] ,int p, int q){
    if(p<q){
        int j = partition(a,p,q);
        quickSort(a,p,j-1);
        quickSort(a,j+1,q);
    }
}

int main(){
    int n;
    printf("\n Enter size:");
    scanf("%d",&n);
    int a[n];
    printf("Enter elements:");
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    quickSort(a,0,n-1);
    printf("\n Sorted Array:");
    for(int i=0;i<n;i++){
        printf("%d \t",a[i]);
    }
    printf("\n");
    return 0;
}