#include<stdio.h>
void swap(int arr[],int index1,int index2) //swapping function
{
	int temp=arr[index1];
	arr[index1]=arr[index2];
	arr[index2]=temp;
}
int partition(int arr[],int low,int high)//partition function
{
	int partitionIndex=arr[high]; //assumption
	int i=low-1;
	int j;
	for(j=low;j<high;j++)
	{
		if(arr[j]<=partitionIndex)
		{
			i++;
			swap(arr,i,j);
		}
	}
	swap(arr,i+1,high);
	return i+1;
}
void quickSort(int arr[],int low,int high) //recursive function
{
	int partitionIndex;
	if(low<high)
	{
		partitionIndex=partition(arr,low,high);
		quickSort(arr,low,partitionIndex-1);
		quickSort(arr,partitionIndex+1,high);
	}
}
void displayArray(char msg[],int arr[],int len) //display function
{
	int i;
	printf("%s\n",msg);
	for(i=0;i<len;i++)
	printf("%d ",arr[i]);
	printf("\n");
}
int main() //main function
{
	int arr[]={81,18,33,14,22,45,12,8,10,6,50,72};
	int len=sizeof(arr)/sizeof(arr[0]);
	displayArray("before sort::",arr,len);
	quickSort(arr,0,len-1);
	displayArray("after sort::",arr,len);
	return 0;
}