#include <stdio.h>

static size_t select_pivot(int *array,size_t size)
{
	size_t counter = 1;
	while(counter != size && array[counter-1] == array[counter]){
		counter++;
	}
	return counter == size || array[counter-1] < array[counter]?counter
	                                                           :counter-1;
}
static size_t partition(int *array,size_t size)
{
	size_t pivot_pos = select_pivot(array,size)
	    ,first_to_last = 0,last_to_first = size-1;
	int pivot,temp;
	if(pivot_pos == size){
		return 0;
	}
	pivot = array[pivot_pos];
	while(first_to_last < last_to_first){
		while(pivot > array[first_to_last] && first_to_last != size-1){
			first_to_last++;
		}
		while(pivot <= array[last_to_first] && last_to_first){
			last_to_first--;
		}
		if(first_to_last < last_to_first){
			temp = array[first_to_last];
			array[first_to_last] = array[last_to_first];
			array[last_to_first] = temp;
		}
	}
	return first_to_last;
}

void quicksort(int *array,size_t size)
{
	size_t partition_pos = partition(array,size);
	if(partition_pos){
		quicksort(array,partition_pos);
		quicksort(&array[partition_pos],size-partition_pos);
	}
}

int main(void)
{
	int array[8] = {6,6,1,4,2,9,3,7};
	size_t counter = 0;
	quicksort(array,8);
	while(counter != 8){
		printf("%d ",array[counter]);
		counter++;
	}
	return 0;
}