#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);
}