#include "stdio.h"
#include "stdlib.h"
void quicksort(int* array, int lower, int upper)
{
    //if we are at the end point, we're done, do nothing
    //this is the recursive base case
    if (upper - lower <= 1)
    {
        return;
    }
    //choose a pivot, just use last item, it's easiest
    int lower_index = lower;
    int upper_index = upper - 1;
    int pivot = array[upper_index];
    int i = 0;
    int temp = 0;
    for (i = lower; i < upper - 1; ++i)
    {
        if (array[i] <= pivot) //then swap
        {
            temp = array[i];
            array[i] = array[lower_index];
            array[lower_index] = temp;
            ++lower_index;
        }
    }
    //once we're done iterating, throw pivot element into it's final place
    temp = array[upper_index];
    array[upper_index] = array[lower_index];
    array[lower_index] = temp;
    //call quicksort again on list lower and higher than pivot
    quicksort(array, 0, lower_index - 1);
    quicksort(array, lower_index + 1, upper);
}
int main()
{
    int i;
    int length = 8;
    int array[] = {10, 6, 4, 2, 7, 8, 9, 1};
    printf("%s ", "Sorting the list: ");
    for (i = 0; i < length; ++i)
    {
        printf("%i ", array[i]);
    }
    quicksort(array, 0, length);
    printf("\n%s ", "Sorted result: ");
    for (i = 0; i < length; ++i)
    {
        printf("%i ", array[i]);
    }
    printf("\n");
}