#include<stdio.h>
void interchange(int a[],int i,int j){
	int p=a[i];
	a[i]=a[j];
	a[j]=p;
}

int partition(int a[],int m,int p){
	int v=a[m],i=m,j=p;
	
	do{
		do{
			i=i+1;
		}while(a[i] < v);
		do{
			j=j-1;
		}while(a[j] > v);

		if(i<j){
			interchange(a,i,j);
		}
	}while(i < j);
	a[m]=a[j];
	a[j]=v;
	return j;
}



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

int main(){
	int n;
	printf("Enter the size of array : ");
	scanf(" %d",&n);

	int a[n];
	for(int i=0;i<n;i++){
		printf("Enter the element %d : ",(i+1));
		scanf(" %d",&a[i]);		
	}

	QuickSort(a,0,n-1);
	printf("Sorted array is ");
	for(int i=0;i<n;i++){
		printf(" %d",a[i]);
	}

return 0;}