#include <stdio.h>

#include "quicksort.h"

static void swap(int *a, int *b) {
	int t = *a;
	*a = *b;
	*b = t;
}


/*
 *Hoare partition scheme:
algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[ floor((hi + lo) / 2) ]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot
        do
            j := j - 1
        while A[j] > pivot
        if i ≥ j then
            return j
        swap A[i] with A[j]
 */
// Hoare partition scheme, in general is more efficient then Lomuto partition scheme
static int partition_hoare(int * A, int lo, int hi) {
	int pivot = A[(hi + lo) / 2];    // pivot
	int i = lo - 1;
	int j = hi + 1;
	while (1) {
		do  {
			i++;
		} while (A[i] < pivot);
		do  {
			j--;
		} while (A[j] > pivot);

		if (i >=j)
			return j;
		swap(&A[i], &A[j]);
	}

}

void quick_sort_part(int * arr, int low, int high) {
	if (low < high) {

		/* pi is partitioning index, arr[p] is now
		 at right place */
		int pi = partition_hoare(arr, low, high);

		quick_sort_part(arr, low, pi );
		quick_sort_part(arr, pi + 1, high);

	}
}


void quick_sort(int *arr, int a_length) {
	quick_sort_part(arr, 0, a_length-1);
}