Quick Sort Program In C

Quick Sort

• Quick Sort In C
• Algorithm For Quick Sort
• Quick Sort Program In C
• Quick Sort Program Output

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.

Need Python Homework Help: Get Python Homework Help from Epert

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

• 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 

QUICK SORT ALGORITHM

Back to Quick Sort

// 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

Back to Quick Sort

//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 : Quick Sort Program Output

More Informative Posts :

• Counting Sort Program In C
• Heap Sort Program In C
• Merge Sort Program In C
• Bubble Sort Program In C
• Selection Sort Program In C
• Insertion Sort Program In C
• Shell sort Program In C
• Radix Sort Program In C
• Bucket Sort Program In C

Searching And Sorting In C

Other Searching and Sorting technique will be published soon.

SORTING

• Bubble Sort
• Quick Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Counting Sort
• Heap Sort

Merge Sort Program In C

Here I am providing you with Merge Sort program in c.

#include<stdio.h> 

void mergesort(int a[],int i, int j); 
void merge(int a[],int p , int q, int r1); 

int main() 
{ 
 int a[20],i,n,item; 
 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 merge sort
 printf("Items in the array are : "); 
 for(i=0;i<n;i++)
 { 
   printf("%d ",a[i]); 
 } 
 
 //Applying merge sort
 mergesort(a,0,n-1); 
 
 // Displaying elements after merge sort
 printf("\nElements after merge sort : "); 
 for(i=0;i<n;i++) 
 { 
   printf("%d ",a[i]); 
 } 
 return 0; 
} 

void mergesort(int a[],int i, int j) 
{ 
 int mid; 
 if(i>=j) 
 return; 
 
 else 
 { 
   mid=(i+j)/2; 
   mergesort(a,i,mid); 
   mergesort(a,mid+1,j); 
   merge(a,i,mid,j);  
 } 
} 

void merge(int a[],int p , int q, int r) 
{ 
 int n1=q-p+1; 
 int n2=r-q;
 int left[n1+1];
 int right[n2+1]; 

 int i=0;
 int j=0;
 int k=0;
 
 
 for(i=0;i<n1;i++) 
 {
   left[i]=a[p+i]; 
 }
 
 for(i=0;i<n2;i++) 
 {
   right[i]=a[q+i+1];
 }
 
 left[n1]=9999; 
 right[n2]=9999;  
 
 i=0;
 j=0;
 
 for(k=p;k<=r;k++) 
 { 
 
   if(left[i]<right[j]) 
   { 
     a[k]=left[i]; 
     i++; 
   } 
 
   else 
   { 
     a[k]=right[j]; 
     j++; 
   } 
 } 

} 

More Informative Posts :

• Insertion Sort Program In C
• Selection Sort Program In C
• Quick Sort Program In C
• Counting Sort Program In C
• Bubble Sort Program In C
• Heap Sort Program In C
• Bucket Sort Program In C
• Shell Sort Program In C
• Radix Sort Program In C