Quick Sort

Write C Code to implement Quick Sort.

#include <stdio.h>

void quickSort( int[], int, int);
int partition( int[], int, int);


int main()
{
    int i , n ;
    printf("Please Enter Array Length:\n");
    scanf("%d",&n);
    int a[n];
    printf("Enter %d Array Element:\n",n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }

 printf("\n\nUnsorted array is:  ");
 for(i = 0; i < n; ++i) {
  printf(" %d ", a[i]);
 }

 quickSort( a, 0, n-1);

 printf("\n\nSorted array is:  ");
 for(i = 0; i < n ; ++i)
  printf(" %d ", a[i]);
  return 0;

}



void quickSort( int a[], int lower, int upper)
{
   int j;

   if( lower < upper )
   {
       j = split( a, lower, upper);
       quickSort( a, lower, j-1);
       quickSort( a, j+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 ;
}

Share this

Google Facebook Twitter More

• Digg
• Linkedin
• Stumbleupon
• Delicious
• Tumblr
• BufferApp
• Pocket
• Evernote

Unknown