#include <stdio.h>

void myQuickSort(int arr[], int size, int low, int high);
void swapItem(int arr[], int i, int j);
void printarr(int arr[], int length);

int main(void)
{
    int arr[] = { 1, 4, 5, 4, 1, 8, 9, 3, 12, 10, 9, 10};
    int length = 12;
    printarr(arr, length);
    myQuickSort(arr, length, 0, length - 1);
    printarr(arr, length);
}

void myQuickSort(int arr[], int size, int low, int high)
{
    if(low < high) {
        int pivot = arr[high];
        int j = high;
        for(int i = low; i < j; i++)
        {
            if(arr[i] > pivot)
            {
                // don't swap if arr[j-1] is already bigger than pivot
                while(i < j-1 && arr[j-1] > pivot) --j;
                swapItem(arr, i, --j);
                printarr(arr, size);
            }
        }

        // if we swaped before, move pivot to middle
        if(j != high) swapItem(arr, high, j);

        // leave the pivot, sort left and right sides
        myQuickSort(arr, size, low, j-1);
        myQuickSort(arr, size, j+1, high);
    }
}

void swapItem(int arr[], int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void printarr(int arr[], int length)
{
    printf("Print ARR: ");
    for(int i = 0; i < length; i ++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}