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
Dude its the same complexity. You just have combined both the functions, rest is same
#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;
}
#include
#include
void swap(int a[],int x,int y)
{
int temp=a[x];
a[x]=a[y];
a[y]=temp;
}
void quick(int a[],int low,int high)
{
int key;
int i,j,flag=0;
if(low<high)
{
key=a[low];
i=low+1;
j=high;
while(!flag)
{
while((a[i]<key)&&(ikey)
j–;
if(i<j)
swap(a,i,j);
else
flag=1;
}
swap(a,low,j);
quick(a,low,j-1);
quick(a,j+1,high);
}
}
void main()
{
int a[20],n,i;
clrscr();
printf("\n\ ************************ \n QUICK SORT\n ************************\n");
printf("Enter the number of elements:");
scanf("%d",&n);
printf("Enter the elements:\n");
printf("———————-\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quick(a,0,n-1) ;
printf("\n\nThe sorted array is:\n");
printf("———————-");
for(i=0;i<n;i++)
printf("\n%d",a[i]);
getch();
}
HERE MY CODE IS BASED ON THE QUICKSORT ALGORITHM AS IT IS GIVEN IN ——cormen’s—– ALGORITHM BOOK.
# include
int partition(int [] , int , int );
void quicksort(int [] , int , int );
int main()
{
int p,r,l;
int A[8] = {9,8,7,2,5,4,3,6}; //{2,8,7,1,3,5,6,4};
printf(“\n\nBefore quicksort \n\n”);
for(l=1;l<9;l++)
printf("%d ",A[l-1]);
printf("\n\nAfter quicksort \n\n");
quicksort(A , 0 , 7);
for(l=1;l<9;l++)
printf("%d ",A[l-1]);
getchar();
}
void quicksort(int A[], int p, int r)
{
int q;
if (p<r)
{
q = partition(A,p,r);
quicksort(A,p,q-1);
quicksort(A,q+1,r);
}
}
partition(int A[], int p, int r)
{
int x,i,j,temp;
x = A[r];
i = p-1;
for(j=p;j<=(r-1);j++)
{
if(A[j]<=x)
{
i++;
temp = A[j];
A[j] = A[i];
A[i] = temp;
}
}
temp = A[r];
A[r] = A[i+1];
A[i+1] = temp;
return (i+1);
}
#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);
}
}