#include <stdio.h>

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;
}

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;
}

int main(void)
{
	int array[8] = {6,6,1,4,2,9,3,7};
	size_t partition_pos = partition(array,8),counter = 0;
	if(!partition_pos){
		printf("sorted\n");
	}
	else{
		printf("part1 : ");
		while(counter != partition_pos){
			printf("%d ",array[counter]);
			counter++;
		}
		printf("\npart2 : ");
		while(counter != 8){
			printf("%d ",array[counter]);
			counter++;
		}
		printf("\n");
	}
	return 0;
}