Quick Sort Program In C

Quick Sort

QUICK SORT IN C

Back to Quick Sort

Quick Sort is another sorting algorithm that is based on divide and conquer approach. Unlike merge sort that divides input elements according to their position in array, quick sort divides input element according to their values. Here is a three-step divide and conquer process for sorting a typical sub-array.

Divide : Partition or rearrange the array a[p . . r] into two sub-arrays a[ p . . q-1 ] and a[q+1 . . r] such that a[ p . . q-1 ] <= a[q] <= a[q+1 . . r] . Compute the index q as part of this partition procedure. Here a[q] is called the pivot element.


Conquer : Sort the two sub-arrays a[ p . . q-1 ] and a[q+1 . . r]  by recursive calls to quick sort.


Combine : Because the sub-arrays are already sorted, no work is needed to combine them : the entire array a[ p . . r ] is now sorted.


Lets understand Quick Sort with the help of an example : 

Array Elements ( List ) : 2 8 7 1 3 5 6 4

Steps :

  • Select the pivot element ( 4 in this case )
  • Rearrange elements such that elements before pivot element are less than it and element after pivot element are greater than it. This arrangement of elements in accordance with the pivot element is called partition operation.
  • Sort the sub-array recursively. 
Steps for Quick Sort
Steps for Quick Sort
  • The above image shows the partition of Array elements ( Initial list ).
  • Similarly the two sub-array before and after pivot element are partitioned.
  • The complete steps of quick sort is shown below.
Quick Sort Program In C
Quick Sort 

QUICK SORT ALGORITHM


// Algorithm for Quick Sort

QUICKSORT(a, p, r)
  if p<r
    q = PARTITION(a, p, r)
    QUICKSORT(a, p, q-1)
    QUICKSORT(a, q+1, r)

Partitioning the array :

PARTITION(a, p, r)
  x=a[r]
  i=p-1
  
  for j=p to r-1
     if(a[j]<=x)
        i=i+1
        swap a[i] with a[j]
  end loop
  
  swap a[i+1] with a[r]
  return i+1


QUICK SORT PROGRAM IN C


//Quick sort program ( code ) in c

#include<stdio.h> 

void quicksort(int a[],int p, int r); 
int partition(int a[],int p, int r); 

int main() 
{ 
 int a[20],i,n; 
 printf("Enter number of elements in array : "); 
 scanf("%d",&n);
  
 // Inputting elements
 for(i=0;i<n;i++) 
 { 
    printf("Enter number %d: ",i+1); 
    scanf("%d",&a[i]);
 } 
 
 // Displaying Elements before quick sort
 printf("Items in the array are : "); 
 for(i=0;i<n;i++)
 { 
    printf("%d ",a[i]); 
 } 
 
 //Applying quick sort
 quicksort(a,0,n-1); 
 
 // Displaying elements after quick sort
 printf("\nElements after quick sort : "); 
 for(i=0;i<n;i++) 
 { 
    printf("%d ",a[i]); 
 } 
 return 0; 
} 

void quicksort(int a[],int p, int r) 
{
   int q;
   if(p<r)
   {
     // q - index at which pivot element lies
     q=partition(a,p,r);

     // Sorting sub-array recursively
     quicksort(a,p,q-1);
     quicksort(a,q+1,r);
   }
}

int partition(int a[],int p, int r)
{
   int temp;
   int i=p-1;
   int j;

   // pivot element around which partition is done
   int x=a[r];
 
   for(j=p;j<=r-1;j++)
   {
     if(a[j]<=x)
     {
       i=i+1;
       temp=a[i];
       a[i]=a[j];
       a[j]=temp;
     }
   }
 
   temp=a[i+1];
   a[i+1]=a[r];
   a[r]=temp;
   return (i+1);
}

Quick Sort Program Output

Quick Sort Program In C With Output
Quick Sort : Quick Sort Program Output

More Informative Posts :

    Share this

    Related Posts

    Previous
    Next Post »

    2 comments

    comments