Quicksort Program in C, C++

Write a program to implement QuickSort algorithm in C,C++. Quicksort algorithm is mostly asked in interviews. To implement this algorithm efficiently, you need a good understanding of recursion.

Time complexity of sorting algorithms

QuickSort

QuickSort is a divide and conquer algorithm.  It divides large array into smaller sub-arrays and then recursively sort the smaller sub-arrays.

Quicksort algorithm is efficient than other sorting algorithm such as bubble sort, insertion sort, selection sort etc.

QuickSort Time Complexity -

Average Case  - O(nlogn)

Best Case - O(nlogn)

Worst Case - O(n²)

QuickSort Program in C

#include <stdio.h>


 void quick(int arr[],int low,int high){
 
    int pivloc;
 
    if(low >= high) {

       return;

    }

    pivloc = partition(arr,low,high);
 
    quick(arr,low,pivloc-1);
    quick(arr,pivloc+1,high);
 
 }


int partition(int arr[],int low,int high){
 
  int i,j,temp,pivot;
 
  i = low +1;
  j = high;
 
  pivot = arr[low];
 
  while(i<=j){
  
    while((arr[i]<pivot) && (i<high)){
   
     i++;
   
   }
  
   while(arr[j]>pivot){
   
     j--;
   }
  
   if(i<j){
   
    temp = arr[i];
    arr[i] = arr[j];
    arr[j]=temp;
   
    i++;
    j--;
  
   } else {
   
    i++;
   }
  
 }
 
  arr[low] = arr[j];
  arr[j] = pivot;
 
  return j;
 
 
 }

int main(){
 
   int k;

   int arr[]={6,8,2,5,7,3};

   quick(arr,0,5);

   for(k=0;k<6;k++){
 
      printf("%d ",arr[k]);

   }

   return 0; 
}