/*
 * quicksort.c		21 April 2004
 *
 * An exercise implementing C.A.R. Hoare's quicksort.
 * 
 * I learned about the quicksort from:
 * "The C Programming Language, Second Edition" by Brian W. Kernighan
 * and Dennis M. Ritchie (page 87).
 * 
 * The comments in my version use figures of speech which are
 * described in detail in: http://m3peeps.org/qs.htm
 *
 * Note that the sort routine below presumes that any array it
 * is passed has at least one element.
 *
 */
#include <stdlib.h>
#include <stdio.h>

void qs( int array[], int left, int right ) {

	int pivot;	// pivot element.
	int holex;	// hole index.
	int i;

	holex = left + ( right - left ) / 2;
	pivot = array[ holex ];		// get pivot from middle of array.
	array[ holex ] = array[ left ]; // move "hole" to beginning of
	holex = left;			// range we are sorting.

	for ( i = left + 1; i <= right; i++ ) {
		if ( array[ i ] <= pivot ) {
			/* we put the element in the hole,
			 * then we re-establish the hole immediately
			 * to the right of the moved element. */
			array[ holex ] = array[ i ];
			array[ i ] = array[ ++holex ];
		}
	}

	/* At this point, all elements greater than the pivot are to
	 * the right of the hole;  all elements other than the pivot
	 * itself which are less than or equal to the pivot are to
	 * the left of the hole.  We sort the sub-arrays as
	 * necessary.
	 */
	
	if ( holex - left > 1 ) {
		qs( array, left, holex - 1 );
	}
	if ( right - holex > 1 ) {
		qs( array, holex + 1, right );
	}
	array[ holex ] = pivot;

}

int main( int argc, char * argv[] ) {

#define SZ 100
	int number[ SZ ];
	int i;

	srand( time( NULL ) );
	
	for ( i = 0; i < SZ; i++ ) {
		number[ i ] = (int) rand();
	}

	qs( number, 0, SZ - 1 );

	for ( i = 0; i < SZ; i++ ) {
		printf( "%10d\n", number[ i ] );
	}

}