#include <stdio.h>

void quicksort(int arr[], int low, int high);
void print_int_array(int arr[], int len);

int main(void){
    int a[] = {6, 8, 3, 5, 9, 1, 2, 7, 4};
    int len = sizeof(a) / sizeof(a[0]);

    print_int_array(a, len);

    quicksort(a, 0, len - 1);

    print_int_array(a, len);

}

void quicksort(int arr[], int low, int high){
    // temp, i (left), j (right), pivot
    int t, i, j, p;
    if(low < high){
        // set pivot to first element of the main array
        p = low;

        // set "left" array's start to first element of the main array
        i = low;

        // set "right" array's start to last element of the main array
        j = high;

        // while the lowest index (which will increment) remains below the
        // highest (which will decrement)
        while(i < j){
            // if the element in index i is smaller than the pivot,
            // increase the lowest index
            while(arr[i] <= arr[p] && i < high){
                i++;
            }

            // if the element in index i is higher than the pivot, decrease
            // the highest index
            while(arr[j] > arr[p]){
                j--;

            }

            printf("i: %d\nj: %d\n", i, j);

            // if lowest index element remains lower than highest index element, swap them around
            if(i < j){
                printf("swapping %d and %d\n", arr[i], arr[j]);
                t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }

        // swap the pivot and the highest index???
        t = arr[p];
        arr[p] = arr[j];
        arr[j] = t;

        quicksort(arr, low, j - 1); // sort left array
        quicksort(arr, j + 1, high); // sort right array
    }


}

void print_int_array(int arr[], int len){
    for(int i = 0; i < len; i++){
        printf(" %d ", arr[i]);
    }
    printf("\n");
}