#include <stdio.h>


/* Change this two to suit your data type */
typedef int key_t;
void printV( key_t *v, int from, int to ) {
	int i;
	for (i=from; i <= to; i++) 
		printf( "%d ", v[i] );
}

#define SWAP( a, b ) { key_t tmp; tmp = a; a = b ; b = tmp; }
#define DEBUG


/* Partition the array:
 * Return an index r so that anything to the left of r is less
 * than v[r] and anything to the right of it is greater than it
 */ 
int partition( key_t *v, int p, int q ) {
	key_t x = v[q];

	int i = p-1;
	int j;

	for (j=p; j < q; j++) {
		if (v[j] < x) {
			i++;
			SWAP( v[j], v[i] );
		}
	}
	SWAP( v[i+1], v[q] );

#ifdef DEBUG
	printf( "partition(): Range [%d %d]\n", p, q );
	printf( "\t[" ); 
	printV( v, p, i ); 
	printf( "]  " );
	printV( v, i+1, i+1 ); 
	printf( "   [" );
	printV( v, i+2, q );
	printf( "]\n" );
#endif	
	return i+1;

}

/* Quicksort function:
 * Conceptually is very simple: 
 * 	1) Trivial case: Arrays with 0 or 1 elements are sorted
 * 	2) Recursive case: Partition the array, quicksort() both halves
 */
void quicksort( key_t *v, int p, int q ) {
	if (p >= q) 
		return;

#ifdef DEBUG
	printf( "\nquicksort(): Range [%d %d]\n", p, q );
#endif

	int r = partition( v, p, q );
	
	quicksort( v, p, r-1 );
	quicksort( v, r+1, q );
}


int main( void ) {
	key_t v[] = {-4,3,6,1,3,6,2,8};
	quicksort( v, 0, 7 );

	int i;
	for (i=0; i < 8; i++)
		printf( "%d ", v[i] );
	printf( "\n" );
	return 0;
}