Quick Sort in C


Quick sort is developed using a basic idea that it is faster and easier to sort two small arrays than one large array. It uses concepts of divide and conquer.

Quick sort contains a pivot element. We can choose any element as a pivot element. The idea is to keep elements smaller than pivot on left side and the elements which are larger than the pivot on right side.

Steps involved in quick sort

  1. In the first step we choose a pivot element.
  2. In the second step take two variables 'i' and 'j'.
  3. Initial element of an array is assigned to 'i' and the last element is assigned to 'j'.
  4. Now, we need to find an element which is greater than our pivot element with the help of 'i'(by incrementing 'i').
  5. We also need to find an element which is smaller than pivot element with the help of 'j'(by incrementing 'j').

     
  6. The moment when we find the elements which satisfy the criterion described in 4rth and 5th step we swap them.
  7. After swapping we increment 'i' and decrement 'j' to find next eligible pair of elements to swap.

  8. We terminate when 'i' and 'j' becomes equal or they crossover.
  9. In the end the pivot element is replaced with the element at position 'j'.
  10. We get an array which is divide in two parts. The elements on the left side of the pivot are smaller than it and the elements which are on the right side are greater.
  11. Now repeat the all above steps for both sub arrays.
  12. In the end when all sub arrays are left with one element only then we get a final array which is sorted.

Quick Sort Implementation

Now we are going to implement quick sort in C. We will sort the array give bellow.

int a[] = {10, 3, 8, 14, 24, 19, 2};

Find the divide point using the split function.

i = split_array(a, lower, upper);

split_array() function

  • Prototype of function
    int split_array(int*, int, int);
  • Function definition
    int split_array(int a[], int lower, int upper){
    }
  • Make lowest element as pivot.
    pivot = a[lower];
    Note: You can choose any element as a pivot.
  • Assign 'i' and 'j'
     i = lower+1;
     j = upper;
  • Increment 'i' and decrement 'j' till you find an element such that a[i]>pivot and a[j]<pivot.
     while(a[i]<pivot)
            i++;
            while(a[j]>pivot)
            j--;
  • Swap the elements at 'i' and 'j' after finding suitable match. Make sure to check for condition that i<j.
      if(i<j){
               temp = a[j];
               a[j]= a[i];
               a[i] = temp;
            }
  • Swap the element at 'j' position with pivot.
    temp = a[lower];
    a[lower] = a[j];
    a[j] = temp;
  • Now 'j' is having the pivot element. We can divide the array on the basis of position on pivot element.

Complete code

#include <stdio.h>
#include <string.h>
void quickSort(int*, int, int);
int split_array(int*, int, int);
int main(void)
{
    int a[] = {10, 3, 8, 14, 24, 19, 2};
    int i;
   
    quickSort(a, 0, 6);
     for(i=0;i<7;i++){
         printf("%d, ", a[i]);
     }
     return 0;
     
    }
  
int split_array(int a[], int lower, int upper){
    int pivot, i, j, temp;
    pivot = a[lower];
    i = lower+1;
    j = upper;
    
    while(i<=j){
        while(a[i]<pivot)
        i++;
        while(a[j]>pivot)
        j--;
        if(i<j){
           temp = a[j];
           a[j]= a[i];
           a[i] = temp;
        }
    }
    
    temp = a[lower];
    a[lower] = a[j];
    a[j] = temp;
    return j;
}
void quickSort(int a[], int lower, int upper){
    int i;
    if(upper>lower){
    i = split_array(a, lower, upper);
    quickSort(a, lower, i-1);
    quickSort(a, i+1, upper);
    }
}  

Output: