More generic sorting algorithm: using namespaces

I am currently reading The C++ Programming Language (Special Edition) and am learning about using templates. One of the exercises asks you to program a generic version of quicksort. I am hoping to build a namespace called Sorters that has a class for each sorter, just for learning purposes. I would like to also be able to sort objects and avoid copying them when performing swaps, etc.

Basically I am looking for advice on how to improve my algorithm/namespace to work with a wide variety of objects. For now I will stick with quicksort to keep things simple.

```
#include
#include
#include
#include
#include
#include
#include
/ Namespace for all types of sorters /
namespace Sorters
{
using std::vector;
using std::copy;
using std::ostream;
using std::ostream_iterator;
using std::cout;
using std::endl;
using std::next_permutation;
using std::distance;

template class QSorter
{
/ Member functions are described where they are defined /
public:
void PermTester( int N );
void Qsort( typename vector::iterator l, typename vector::iterator r );
private:
vector m_data;
void Swap( typename vector::iterator l, typename vector::iterator r );
friend ostream& operator( cout, " " ) );
return stream;
}
};

/* This method is for testing my algorithm, it create 1!, 2!, ... N! permutations
for an ordered set of N elements and then passes that to quick sort to be sorted */
template
void QSorter::PermTester( int N )
{
for( int x=0; x( x );
vector perm;
for( int y=0; y
void QSorter::Swap( typename vector::iterator l, typename vector::iterator r )
{
T tmp = (*r);
(r) = (l);
(*l) = tmp;
}

/ This is the actual quick sort, it gets the pivot from the middle of the partition /
/* swaps the left element of partition with pivo

First thing your swap is going to kill you on expensive swaps:

template
void QSorter::Swap( typename vector::iterator l, typename vector::iterator r )
{
    T tmp = (*r);
    (*r) = (*l);
    (*l) = tmp;
}

Use swap() on the de-referenced types.

template
void QSorter::Swap( typename vector::iterator l, typename vector::iterator r )
{
    // If the type T has a defined swap() function this will be used.
    // otherwise it will use std::swap which does what your original code did.
    swap(*l, *r);
}

Here you are making an un-necessary swap. and a copy.

T pivot = (*it_pivot);
        Swap( l,it_pivot );

You don't need to choose the value at the pivot point as the value to pivot on. Since the value is random just choose the value at (*l) as the pivot point (this also makes sure it will not be moved as less or equal to the pivot point goes on the left. Thus you can reduce the above too:

T& pivot = *l;

All things that are less than or equal go on the left. All things greater go on the right. Thus this statement does not work:

while( (*it_r) >=  pivot && it_l < it_r ) --it_r;
                       // ^^^^  // Your sets or joined.

You can make a different choice on how to split the sets but they should be mutually exclusive sets objects should either be on the right or left there should not be objects that can appear on both.

No need to do a continue/swap if they are equal!

/*1*/        while( it_l <= it_r )  // If they are equal no need to continue 

 /*2*/           if( it_l <= it_r ) // If they are equal no need to swap

Looks like this:

void QSorter::Qsort( typename vector::iterator l, typename vector::iterator r ) 
{
    if (distance(l,r) ::iterator it_l = l+1;    // +1 because pivot is at l
    typename vector::iterator it_r = r-1;    // -1 because r is outside partition

    while( it_l   pivot && it_l < it_r ) { --it_r;}
        if( it_l < it_r ) 
        {
            Swap( it_l,it_r );
        }
    }
    // Move the pivot element to the pivot point.
    // Optimized if the values are the same no need to swap
    if (*lt_l < *l) // Note we need to do this because we choose not 
    {               // to include the pivot point in the loop of comparisons by doing 
                    // lt = l + 1 above. Thus small arrays of two elements may not be sorted
        Swap(lt_l, l);
    }   
    Qsort( l, it_l );   // Sort things smaller than the pivot point
    Qsort( it_r+1, r ); // Sort things larger than the pivot point
                        // Note: Do not include pivot point in recursive sort
}

StackExchange Code Review Q#3932, answer score: 4