Более универсальный алгоритм сортировки: использование пространств имен


Я сейчас читаю на Си++ программирования язык (специальный выпуск) и учусь об использовании шаблонов. Одно из упражнений просит вас программа универсальный вариант быстрой сортировки. Я надеялся, что для построения пространства имен сортировщиков , что есть класс для каждого сортировщика, только в учебных целях. Я хотел бы также иметь возможность сортировать объекты и избежать их копирования при выполнении свопы и т. д.

В основном я ищу советы о том, как улучшить мой алгоритм/пространство имен для работы с широким спектром объектов. Сейчас я буду придерживаться быстрой сортировки, чтобы держать вещи простыми.

#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 );
}


Комментарии
1 ответ

Первым делом ваш своп убьет тебя на дорогих свопов:

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

Используйте функцию swap() на де-ссылочные типы.

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);
}

Здесь вы делаете без необходимости замены. а копия.

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

Вам не нужно выбирать значение в точке поворота как значение на оси. Поскольку значение является случайным просто выбрать значение в (*л) в качестве опорной точки (это также гарантирует, что он не будет перемещен в менее или равна опорной точки идет слева. Таким образом, вы можете уменьшить это слишком:

        T& pivot = *l;

Все, что меньше или равно перейти на левом. Все больше идти на право. Таким образом, это утверждение не работает:

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

Вы можете сделать другой выбор, как для разделения наборов, но они должны быть взаимоисключающими наборами объектов, должны быть справа или слева не должно быть объектов, которые могут появиться на обоих.

Не нужно даже делать и впредь/подкачки, если они равны!

/*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

Выглядит это так:

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
}

4
ответ дан 7 августа 2011 в 07:08 Источник Поделиться