#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "../hdr.h"

static int partition(int numbers[], int left, int right);
void quick_sort(int numbers[], int left, int right);

#define NCOUNT 10

int
main(int argc, char *argv[])
{
    int i;
    int numbers[NCOUNT];

    srand(time(NULL));
    for (i = 0; i < NCOUNT; i++)
        numbers[i] = rand() % 100;

    print_array(numbers, NCOUNT);
    quick_sort(numbers, 0, NCOUNT-1);
    print_array(numbers, NCOUNT);

    exit(0);
}

static int
partition(int numbers[], int left, int right)
{
    int pivot_index, pivot;

    if (left >= right)
        return -1;

    pivot_index = left;
    pivot = numbers[pivot_index];
    left++;

    while (1) {
        while (left <= right && numbers[left] <= pivot)
            left++;

        while (left <= right && numbers[right] >= pivot)
            right--;

        if (left < right)
            swap(numbers, left++, right--);
        else
            break;
    }
    swap(numbers, right, pivot_index);
    return right;
}

void
quick_sort(int numbers[], int left, int right)
{
    int pivot;

    if (left >= right)
        return;

    pivot = partition(numbers, left, right);
    quick_sort(numbers, left, pivot-1);
    quick_sort(numbers, pivot+1, right);
}