Sign in to follow this  
JimmyDeemo

Template Sorting Question

Recommended Posts

I have been doing a quicksort algorithm, detailed here. Now i'm trying to templetize it. My problem is that i dereference an iterator to get the pivot 'element'. I'm not sure how to make this work with an unknown type, as before it was just for a vector of int's. Could anyone help me out, and perhaps comment on my template use below?
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 );
}



Share this post


Link to post
Share on other sites
You can get the value_type from the iterator:

typename BiDirectionalItor::value_type pivot_value = *middle;


Now, you'll have a problem if BiDirectionalItor happens to be a simple pointer. In this case you'll probably have to avoid declaring instances of value_type, or provide overloads. I also think, auto keyword in C++0x is going to solve this inconvenience...

Share this post


Link to post
Share on other sites
Obviously i'd like the template function to be as portable as possible. Do you think that with my naming of the template arguements i'm giving good indication to any possible users that its intended for STL containers and iterators? Or should i try and limit how people can use the code? (i know thats kind of backward for a template, but you get my meaning)

Cheers for the help.

Share this post


Link to post
Share on other sites
Actually, looking at the STL implementation, you should use this to determine the value_type:

typename std::iterator_traits<BiDirectionalItor>::value_type pivot_value = *middle;


That would also work for pointers, since iterator_traits has a specialization for them.

Share this post


Link to post
Share on other sites
Quote:
Original post by Spoonbender
so the only sensible reason I can see for writing your own is as a learning experience.


Thats exactly what i'm doing Spoonbender, if you read my previous thread i think i state that somewhere. I'd like anyone who looks at it to know that i understand how such things work. Also that i can take portability into consideration.

Great visitor, thanks for the help.

Share this post


Link to post
Share on other sites
Quote:
Original post by JimmyDeemo
Thats exactly what i'm doing Spoonbender, if you read my previous thread i think i state that somewhere. I'd like anyone who looks at it to know that i understand how such things work. Also that i can take portability into consideration.


You know, there's a high probability that your compiler implementation actually provides source code for std::sort...

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this