Writing programs for sorting of a given set of numbers is one of the common programming tasks. Various types of sorting techniques like selection sort, inserting sort and quick sort are quite popular. Here C code for Quick sort is being presented. Here, in each iteration the array is subdivided into 2 arrays, and hence is a good example of Divide and Conquer algorithm. The program has the worst case complexity of O(n²) and an average and best case complexity of O(n logn).
Following is the C code implementation of Quick Sort algorithm :
#include "stdio.h"
int split ( int*, int, int ) ;
void main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;
void quicksort ( int *, int, int ) ;
quicksort ( arr, 0, 9 ) ;
printf ( "\nArray after sorting:\n") ;
for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", arr[i] ) ;
}
void quicksort ( int a[ ], int lower, int upper )
{
int i ;
if ( upper > lower )
{
i = split ( a, lower, upper ) ;
quicksort ( a, lower, i - 1 ) ;
quicksort ( a, i + 1, upper ) ;
}
}
int split ( int a[ ], int lower, int upper )
{
int i, p, q, t ;
p = lower + 1 ;
q = upper ;
i = a[lower] ;
while ( q >= p )
{
while ( a[p] < i )
p++ ;
while ( a[q] > i )
q-- ;
if ( q > p )
{
t = a[p] ;
a[p] = a[q] ;
a[q] = t ;
}
}
t = a[lower] ;
a[lower] = a[q] ;
a[q] = t ;
return q ;
}
Posted in 
Tags: 
this implementation becames very slow when array is long. Here is much faster implementation:
http://www.algorithmist.com/index.php/Quicksort.c
#include
void quicksort(int [10],int,int);
int main(){
int x[20],size,i;
printf(“Enter size of the array: “);
scanf(“%d”,&size);
printf(“Enter %d elements: “,size);
for(i=0;i<size;i++)
scanf("%d",&x[i]);
quicksort(x,0,size-1);
printf("Sorted elements: ");
for(i=0;i<size;i++)
printf(" %d",x[i]);
return 0;
}
void quicksort(int x[10],int first,int last){
int pivot,j,temp,i;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(x[i]<=x[pivot]&&ix[pivot])
j–;
if(i<j){
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;
quicksort(x,first,j-1);
quicksort(x,j+1,last);
}
}
Try mine above!!
a new approach…
//implementing quicksort…..with arrays….ver …0.1
#include
#include
int *quicksort(int *a,int size);
int printarray(int *a,int size);
int *xrealloc(int *b,int osizze,int size);
int main()
{
int size,*a,i;
printf(“enter how many elements:”);
scanf(“%d”,&size);
a=(int *)malloc(size*sizeof(int));
i=1;
while(i<=size)
{
printf("enter element number %d :",i);
scanf("%d",a+i-1);
i++;
}
printarray(a,size);
a=quicksort(a,size);
printf("\nthe sorted sequence—");
printarray(a,size);
}
int *quicksort(int *a,int size)
{
if(size==0)
{
return a;
}
if(size==1)
{
return a;
}
int pivot=0;
int *b,*c;
int i,bsize,csize,j;
pivot=*a;
b=(int *)malloc(size*sizeof(int));
c=(int *)malloc(size*sizeof(int));
i=1;
bsize=0;
csize=0;
while(i<=size-1)
{
if(*(a+i)<pivot)
{
*(b+bsize)=*(a+i);
bsize++;
}
else
{
*(c+csize)=*(a+i);
csize++;
}
i++;
}
b=quicksort(b,bsize);
c=quicksort(c,csize);
b=xrealloc(b,bsize,size);
i=bsize+1;
j=0;
*(b+bsize)=pivot;
while(i<=size-1)
{
*(b+i)=*(c+j);
i++;
j++;
}
free(c);
free(a);
return b;
}
int printarray(int *a,int size)
{
int i;
i=0;
printf("\n{");
while(i<=size-1)
{
printf(" %d ",*(a+i));
i++;
}
printf("}\n");
}
int *xrealloc(int *b,int osize,int size)
{
if(osize==size)
{
return b;
}
int *c,i;
c=(int *)malloc(size*sizeof(int));
i=0;
while(i<=osize-1)
{
*(c+i)=*(b+i);
i++;
}
free(b);
return c;
}