Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

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 quick sort. I am hoping to build a name space 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 quick sort to keep things simple.

Additionally, if I can get additional feed back on my style that would be greatly appreciated as well. Below is the code.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <ctime>
#include <assert.h>
/* 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 T> class QSorter 
    {
        /* Member functions are described where they are defined */
        public:
            void PermTester( int N );
            void Qsort( typename vector<T>::iterator l, typename vector<T>::iterator r );
        private:
            vector<T> m_data;
            void Swap( typename vector<T>::iterator l, typename vector<T>::iterator r );
            friend ostream& operator<< ( ostream &stream, QSorter &qs )
            {
                copy( qs.m_data.begin( ), qs.m_data.end( ), ostream_iterator<T>( 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<class T> 
    void QSorter<T>::PermTester( int N ) 
    {
        for( int x=0; x<=N; x++ )
        {
            m_data = vector<T>( x );
            vector<T> perm;
            for( int y=0; y<x; y++ ) 
            {
                perm.push_back( y+1 );
            }
            do 
            {
                copy( perm.begin( ),perm.end( ),m_data.begin( ) );
                cout << "*****************************************************************" << endl;
                cout << "Going to Sort: " << (*this) << endl;
                cout << "*****************************************************************" << endl;
                Qsort( m_data.begin( ), m_data.end( ) );
                cout << "*****************************************************************" << endl;
                cout << "Sorted: " << (*this) << endl;
                cout << "*****************************************************************" << endl;

            } while( next_permutation( perm.begin( ),perm.end( ) ) ); 
        }
        m_data.clear( );
    }

    /* This method is designed to swap two elements pointed to by iterators */
    template<class T>
    void QSorter<T>::Swap( typename vector<T>::iterator l, typename vector<T>::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 pivot, then calculates/sorts a left and        */
    /* and right partition around that pivot. The pivot is moved back between left an*/
    /* right partitions and the sort is then called on the left and right side of the*/
    /* partitions.*/
    template<class T> 
    void QSorter<T>::Qsort( typename vector<T>::iterator l, typename vector<T>::iterator r ) 
    {
        if( r<=l+1 ) 
        {
        } 
        else
        {
            typename vector<T>::iterator it_pivot =l+distance(l,r)/2;
            T pivot = (*it_pivot);
            Swap( l,it_pivot );
            typename vector<T>::iterator it_l = l+1;    // +1 because pivot is at l
            typename vector<T>::iterator it_r = r-1;    // -1 because r is outside partition
            while( it_l <= it_r ) 
            {
                while( (*it_l) <= pivot && it_l <= it_r ) ++it_l;
                while( (*it_r) >= pivot && it_l <= it_r ) --it_r;
                if( it_l <= it_r ) 
                {
                    Swap( it_l,it_r );
                }
            }
            Swap( l,it_r );
            Qsort( l, it_r );
            Qsort( it_r, r );
        }
    }
}

int main( int argc, char *argv[ ] ) {
    Sorters::QSorter<float> qs;
    qs.PermTester( 5 );
}
share|improve this question

1 Answer

up vote 1 down vote accepted

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

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

Use swap() on the de-referenced types.

template<class T>
void QSorter<T>::Swap( typename vector<T>::iterator l, typename vector<T>::iterator r )
{
    // If the type T has a defined swap() function this will be used.
    // otherwise it will use std::swap<T> 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<T>::Qsort( typename vector<T>::iterator l, typename vector<T>::iterator r ) 
{
    if (distance(l,r) < 2)
    {    return;
    }
    // return quickly rather than using an else block.
    // Personally I think this makes the code look cleaner.
    //
    // Note: Because of RAII it is not bad to return early from a C++ function.
    //       Though it is considered bad in C (because you need to consider resource release).


    T& pivot = (*l);

    typename vector<T>::iterator it_l = l+1;    // +1 because pivot is at l
    typename vector<T>::iterator it_r = r-1;    // -1 because r is outside partition

    while( it_l < it_r ) 
    {
        while( (*it_l) <= pivot && it_l < it_r ) { ++it_l;}
        while( (*it_r) >  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
}
share|improve this answer
I appreciate your emphasis on increasing performance, very helpful. – Matthew Hoggan Aug 8 '11 at 4:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.