Public Group

# Template Sorting Question

This topic is 3690 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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 on other sites
Why does portability matter? You're reinventing the wheel. C++ already has a portable sort function, so the only sensible reason I can see for writing your own is as a learning experience.

##### 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 on other sites
Quote:
 Original post by Spoonbenderso 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 on other sites
Quote:
 Original post by JimmyDeemoThats 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 on other sites
Silly me of course it does. The syntax is hard to read but i will certainly help my learning.

1. 1
2. 2
Rutin
20
3. 3
khawk
16
4. 4
A4L
14
5. 5

• 11
• 16
• 26
• 10
• 11
• ### Forum Statistics

• Total Topics
633756
• Total Posts
3013708
×