int main()
{
	//Seed the random number generator.
	srand(static_cast<unsigned>(time(0)));

	for( int i = 0; i < 200; ++i )
	{
		g_intNumbers.push_back( (rand()%100)+1 );
		g_floatNumbers.push_back( static_cast<float>((rand()%100)+1) );
	}

	quicksort( g_intNumbers );
	quicksort( g_floatNumbers );

	return 0;
}

template <class STLCont>
void quicksort( STLCont &data )
{
	if( data.size() > 1 )
		q_sort( data.begin(), data.end() );
}

template <class BiDirectionalItor>
void q_sort( BiDirectionalItor start, BiDirectionalItor end )
{
	//First check for a sorted partition i.e. Size of one element.
	if( end - start == 1 )
		return;

	//Create some iter's to move,
	BiDirectionalItor front = start;
	BiDirectionalItor back = end - 1;
	//Find the middle (approx) element
	BiDirectionalItor middle = start + (end - start)/2;

	//Bubble sort so the pivot is now the median of the three.
	//Only need three (possible) swaps.
	if( *middle < *front )
	{
		std::swap( *middle, *front );
	}
	if( *back < *front )
	{
		std::swap( *back, *front );
	}
	if( *back < *middle )
	{
		std::swap( *back, *middle );
	}

	//If we only have three elements then we are sorted
	if( end - start <= 3 )
		return;

	int pivot_value = *middle; //Problem here, currently get a 'loss of data' conversion warning.
	
	//Loop until our markers have passed each other
	do
	{
		do
		{
			++front;
		}
		while( *front < pivot_value );

		do
		{
			--back;
		}
		while( *back > pivot_value );

		if( front < back )
		{
			//Two elements are out of order.
			std::swap( *front, *back );
		}
	}
	while( front < back );

	
	//The data is approx split into two, lets sort each partition.
	q_sort( start, front );
	q_sort( front, end );
}