//Quick sorting using Recursion
#include<stdio.h>
#include<stdlib.h>
//Prototypes of functions used
int * input(int *,int);
int * sort(int *,int);
void display(int*,int);
int main()
{
int *a,n;
printf(“Enter number of numbers you want to sort?\n”);
scanf(“%d”,&n);
a = input(a,n);
a = sort(a,n);//call to quick sort
display(a,n);
return 0;
}
//Function to input an array
int * input(int *a,int n)
{
int i;
printf(“Enter %d elements\n”,n);
a = (int *)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);
return a;
}
//Function to Quick Sort
int * sort(int *data,int n)
{
int too_small_index,too_big_index,pivot,temp;
pivot = 0;//Index of pivot element
too_big_index = pivot + 1;
too_small_index = n – 1;
//Terminating condition for recursive call
if(too_big_index>too_small_index)
return data;
do
{
//Step 1
while(*(data + too_big_index)<=*(data + pivot))
++too_big_index;
//Step 2
while(*(data + too_small_index)>*(data + pivot))
–too_small_index;
//Step 3
if(too_big_index<too_small_index)
{
temp = *(data + too_big_index);
*(data + too_big_index) = *(data + too_small_index);
*(data+too_small_index) = temp;
}
}while(too_small_index>too_big_index);//Step 4
//Step 5
temp = *(data + too_small_index);
*(data + too_small_index) = *(data+pivot);
*(data+pivot) = temp;
//Sorting left side of array
if(too_small_index!=too_big_index)
data = sort(data,too_small_index);
//sorting right side of array
sort((data+too_small_index+1),n-too_small_index-1);
return data;
}
//Function to display the array
void display(int*a,int n )
{
int i;
printf(“\nSorted list\n”);
for(i=0;i<n;i++)
printf(“%d\t”,*(a+i));
}