Quick Sort is a sorting algorithm that works on the Divide and Conquer technique. It is the widely used algorithm that sorts elements in n log n average time.

Key Terms

Partition: -

  • A function that takes 3 arguments, an array, low index, and high index.
  • Selects a pivot (any random element) from the array.
  • Using loops: Swap every element <= pivot to the left side of the pivot and elements>pivot to the right side of the pivot.
  • At last, when the loop ends you will get the correct position of the pivot.
  • Swap the pivot element with that index and return the index.
Partition 1PivotPartition 2
values <= pivotKey elementvalues > pivot

Quick Sort Function

A function that recursively calls itself with an array, lower index, and higher index

  • Call the partition function in each call and put an element in its correct position
  • Divides the array from the pivot index and then calls quick sort for the left subarray and right subarray.

Code

#include <stdio.h>

void swap(int *x, int *y){
    int temp = *x;
    *x = *y;
    *y = temp;
}

// Printing array
void printArray(int arr[], int n){
    for (int i = 0; i < n; i++){
        printf("%d ", arr[i]);
    }
}

int partition(int arr[], int low, int high){
    int pivot = arr[low];   // Taking 0 index element as pivot
    int i = low + 1; // It iterate the array and find element <= pivot
    int j = high;   // It iterates and find element > pivot

    // This loop run until i>j
    do{
        // this loop finds first index of element <= pivot (Left to right)
        while (arr[i] <= pivot){ 
            i++;
        }
        // this loop find element > pivot (right to left)
        while (arr[j] > pivot){
            j--; 
        }
        
        // Swaping elements so if i<j
        if (i < j){
            swap(&arr[i], &arr[j]);
        }
    } while (i < j);

    // This swap place the pivot at its correct position
    swap(&arr[low], &arr[j]);
    // return the index of correct position of pivot element
    return j;
}

void quickSort(int arr[], int low, int high){
    int partationIndex; 
    // partition index is the index of pivot element which is in its correct position
    if (low < high){
        partationIndex = partition(arr, low, high);
        // Sorting left subarray
        quickSort(arr, low, partationIndex - 1);
        // Sorting right subarray
        quickSort(arr, partationIndex + 1, high);
    }
}

void main(){
    int arr[] = {5, 20, 4, 16, 2};
    int n = 5;
    quickSort(arr, 0, n - 1);
    printArray(arr, n);
}