#include<stdio.h>
 
void quicksort(int[],int,int);
int partition(int[],int,int);
void swap(int*,int*);
 
int main()
{
	int n,i;
    printf("Enter Array size\n");
	scanf("%d",&n);
	int arr[n];
	printf("Enter the array element\n");
	for(i=0;i<n;i++)
	scanf("%d",&arr[i]);
	quicksort(arr,0,n-1);
	printf("after the Quick sort\n");
	for(i=0;i<n;i++)
	printf("%d\t",arr[i]);
	printf("\n");
	return 0;
}
 
void quicksort(int arr[],int lb ,int ub)
{
	if(lb<ub)
	{
		int pIndex = partition(arr,lb, ub);
		quicksort(arr,lb,pIndex-1);
		quicksort(arr,pIndex+1,ub);
	}
}
 
int partition(int arr[],int lb ,int ub)
{
    int pIndex =lb;
    int pivot=arr[ub];
    int i;
    for(i=lb;i<ub;i++)
	{
	    if(arr[i]<pivot)
		{
		    swap(&arr[i],&arr[pIndex]);
		    pIndex++;	
		}
	}	
	swap(&arr[ub],&arr[pIndex]);
	return pIndex;	
}
 
void swap(int *x,int*y)
{
    int temp=*x;
	*x=*y;
	*y=temp;
}
 

I2luY2x1ZGU8c3RkaW8uaD4KCnZvaWQgcXVpY2tzb3J0KGludFtdLGludCxpbnQpOwppbnQgcGFydGl0aW9uKGludFtdLGludCxpbnQpOwp2b2lkIHN3YXAoaW50KixpbnQqKTsKCmludCBtYWluKCkKewoJaW50IG4saTsKICAgIHByaW50ZigiRW50ZXIgQXJyYXkgc2l6ZVxuIik7CglzY2FuZigiJWQiLCZuKTsKCWludCBhcnJbbl07CglwcmludGYoIkVudGVyIHRoZSBhcnJheSBlbGVtZW50XG4iKTsKCWZvcihpPTA7aTxuO2krKykKCXNjYW5mKCIlZCIsJmFycltpXSk7CglxdWlja3NvcnQoYXJyLDAsbi0xKTsKCXByaW50ZigiYWZ0ZXIgdGhlIFF1aWNrIHNvcnRcbiIpOwoJZm9yKGk9MDtpPG47aSsrKQoJcHJpbnRmKCIlZFx0IixhcnJbaV0pOwoJcHJpbnRmKCJcbiIpOwoJcmV0dXJuIDA7Cn0KCnZvaWQgcXVpY2tzb3J0KGludCBhcnJbXSxpbnQgbGIgLGludCB1YikKewoJaWYobGI8dWIpCgl7CgkJaW50IHBJbmRleCA9IHBhcnRpdGlvbihhcnIsbGIsIHViKTsKCQlxdWlja3NvcnQoYXJyLGxiLHBJbmRleC0xKTsKCQlxdWlja3NvcnQoYXJyLHBJbmRleCsxLHViKTsKCX0KfQoKaW50IHBhcnRpdGlvbihpbnQgYXJyW10saW50IGxiICxpbnQgdWIpCnsKICAgIGludCBwSW5kZXggPWxiOwogICAgaW50IHBpdm90PWFyclt1Yl07CiAgICBpbnQgaTsKICAgIGZvcihpPWxiO2k8dWI7aSsrKQoJewoJICAgIGlmKGFycltpXTxwaXZvdCkKCQl7CgkJICAgIHN3YXAoJmFycltpXSwmYXJyW3BJbmRleF0pOwoJCSAgICBwSW5kZXgrKzsJCgkJfQoJfQkKCXN3YXAoJmFyclt1Yl0sJmFycltwSW5kZXhdKTsKCXJldHVybiBwSW5kZXg7CQp9Cgp2b2lkIHN3YXAoaW50ICp4LGludCp5KQp7CiAgICBpbnQgdGVtcD0qeDsKCSp4PSp5OwoJKnk9dGVtcDsKfQo=