C Code for Quick Sort

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 ;
}


Related Posts

Share

Filed Under: CCodes

Tags:

About the Author: Software Engineer - Advanced Search & Recommendation at Rovi

RSSComments (9)

Leave a Reply | Trackback URL

  1. br0d3r says:

    this implementation becames very slow when array is long. Here is much faster implementation:
    http://www.algorithmist.com/index.php/Quicksort.c

  2. webdevil_coder says:

    #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);

    }
    }

  3. webdevil_coder says:

    Try mine above!!

  4. SSPK says:

    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;
    }

  5. Vinayak Shenoy says:

    #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();
    }

  6. venu gopal says:

    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);
    }

  7. #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);

    }
    }

  8. aditya jethwa says:

    qs(int a[],int lb,int ub)
    {
    int key,i,j,tmp;
    if(lb<ub)
    {
    key=a[lb];
    i=lb;
    j=ub;
    while(i<j)
    {
    while(a[i]<=key && i=key && j>=lb)
    j–;
    if(i<j)
    {
    tmp=a[i];
    a[i]=a[j];
    a[j]=tmp;
    }
    tmp=a[j];
    a[j]=a[lb];
    a[lb]=tmp;
    qs(a,lb,j-1);
    qs(a,j+1,ub);
    }
    }

    }
    //THIS IS SIMPLER

Leave a Reply

*

AWSOM Powered