#include <stdio.h>
#include <stdlib.h>
/* the partition function - it takes a pivot element (the last element in this case) and moves all smaller elements to its left side and all larger elements to its right side. */
int partition(int a[],int l,int h)
{ int pivot,i,j,temp;
pivot = a[h]; // setting the last element as the pivot element
i = l-1;
for(j=l;j<=h-1;j++)
{
if(a[j]<=pivot)
{
i++;
/* the swap block - we can use a swap function too instead of this block as the main purpose of this block is to basically swap
a[i] and a[j] */
{
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
}
/* this is another swap block - again, we can use a swap function instead of this block. The main purpose of this block is to swap
a[i+1] and a[h] */
{
temp = a[i+1];
a[i+1] = a[h];
a[h] = temp;
}
return i+1;
}
/* The recursive function quicksort */
void quicksort(int a[],int l,int h)
{
if(l<h)
{
int pivot = partition(a,l,h); // set the pivot element using the partition function
quicksort(a,l,pivot-1); // sort the left side of pivot element
quicksort(a,pivot+1,h); // sort the right side of pivot element
}
}
/* The main function */
int main()
{ int size,i,a[20];
printf("enter size of array : ");
scanf("%d",&size);
printf("enter array elements : "); // enter the array
for(i=0;i<size;i++)scanf("%d",&a[i]);
quicksort(a,0,size-1); // calling the quicksort function
printf("sorted array : \n"); // printing the sorted array
for(i=0;i<size;i++)printf(" %d ",a[i]);
return 0;
}