#include <stdio.h>
#include <stdlib.h>


// prototype declaration
void quickSort(int* arr, int low, int high);
int _partition(int* arr, int low, int high);

// quick sort function
void quickSort(int* arr, int low, int high){
    if(low < high){
        int p = _partition(arr, low, high);
        quickSort(arr, low, p - 1);
        quickSort(arr, p + 1, high);
    }
}

// partition function
int _partition(int* arr, int low, int high){
    int pivot = arr[high];
    int i = low;
    for(int j = low; j < high; j++){
        if(arr[j] < pivot){
                // swap
            int temp = arr[i];
            arr[i++] = arr[j];
            arr[j] = temp;
        }
    }

    // swap
    int temp = arr[i];
    arr[i] = arr[high];
    arr[high] = temp;

    return i;
}

int main()
{
    int arr[5] = {4, 1, 7, -20, 41};
    quickSort(arr, 0, 4);

    for(int i = 0; i < 5; i++) printf("%d ", arr[i]);
    return 0;
}