Quick Sort

In this tutorial we will learn about Quick sort algorithm.

About Quick Sort

This sorting algorithm uses the idea of divide and conquer. It finds the element called pivot which divides the array into two halves in such a way that elements in the left half are smaller than pivot and elements in the right half are greater than pivot.

We follow three steps recursively:

• Find pivot that divides the array into two halves.
• Quick sort the left half.
• Quick sort the right half.

Algorithm

/**
 * a[0:n-1] is an array of n elements.
 * beg = first index of array
 * end = last index of array
 */
QuickSort(a, beg, end)
Begin
    if beg < end then
        Call PartitionArray(a, beg, end, pivotLoc);    //this will find pivot location
        Call QuickSort(a, beg, pivotLoc - 1 );   //Quick sort left sub array
        Call QuickSort(a, pivotLoc + 1, end);    //Quick sort right sub array
    endif
End

Code in C

#include <stdio.h>
#define SIZE 6  //array size


void partitionArray(int *a, int beg, int end, int *pivotLoc);
void quickSort(int *a, int beg, int end);

int main(){
  int a[SIZE] = {5,2,6,1,3,4};  //unsorted array
  int i;

  quickSort(a, 0, SIZE-1);  //beg = 0 start index of array end = 5 last index of array

  //printing sorted element of array
  for(i = 0; i < SIZE; i++){
    printf("%d\t", a[i]);
  }
  return 0;
}//main() ends here

void quickSort(int *a, int beg, int end){
  int pivotLoc;
  if(beg < end){
    partitionArray(a, beg, end, &pivotLoc);  //this will find the pivot location and partition the array
    quickSort(a, beg, pivotLoc - 1);  //quick sort the left sub array
    quickSort(a, pivotLoc + 1, end);  //quick sort the right sub array
  }
}//quickSort() ends here

void partitionArray(int *a, int beg, int end, int *pivotLoc){
  int left = beg;    //initially left point to the first element of the array
  int right = end;  //initially right point to the last element of the array
  *pivotLoc = left;  //initially pivot point to first element of the array
  int tmp;  //used for swapping values

  while(1){

    //pivot pointing at left
    while(a[*pivotLoc] <= a[right] && *pivotLoc != right){  //pivot element <= right element
      right--;  //move right one position towards left
    }

    if(*pivotLoc == right){  //both left and right pointing at same element of the array
      break;
    }else if(a[*pivotLoc] > a[right]){
      //pivot element greater than right element. swap pivot and right element.
      tmp = a[right];
      a[right] = a[*pivotLoc];
      a[*pivotLoc] = tmp;
      *pivotLoc = right;  //pivot is now pointing to right
    }

    //pivot pointing to right
    while(a[*pivotLoc] >= a[left] && *pivotLoc != left){  //pivot element >= left element
      left++;    //move left one position towards right
    }

    if(*pivotLoc == left){  //both left and right pointing at the same element of the array
      break;
    }else if(a[*pivotLoc] < a[left]){
      //pivot element smaller than left element. swap pivot and left element.
      tmp = a[left];
      a[left] = a[*pivotLoc];
      a[*pivotLoc] = tmp;
      *pivotLoc = left;  //pivot is now pointing to left
    }
  }
}//partitionArray() ends here

Time Complexity

For an array of n elements order of Quick Sort is O(nlog₂n)