шаблонная qsort , что-то не получается :(

Вот сделал сортировку:

template<class T>
void quickSortR(vector<T> a)
{
    long N = a.size();
 
    long i = 0, j = N;      // поставить указатели на исходные места
    T temp, p;
 
    p = a[ N>>1 ];      // центральный элемент
 
    // процедура разделения
    do
    {
        while ( a[i] < p ) i++;
        while ( a[j] > p ) j--;
 
        if (i <= j)
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }
    }
    while ( i<=j );
 
    // рекурсивные вызовы, если есть, что сортировать
    if ( j > 0 ) quickSortR(a, j);
    if ( N > i ) quickSortR(a+i, N-i);
}

Хочу еще в этот метод передавать функцию типа

bool SortByItem (T elem1, T elem2); // типа как у std::sort

Как бы это замутить?

Добавлено 26.10.06, 07:14
Извиняюст, перенесите в Чистый С++, что-то ступил

template<class T>
void quickSortR(vector<T>& a, bool (*fn)(const T&, const T&));

спасиб, Тренер.

Наверное, лучше так:

template<typename T, typename Comparer = std::less<T> >
void quickSortR(vector<T>& a, Comparer cmp=Comparer())
{
    long N = a.size();
 
    long i = 0, j = N;      // поставить указатели на исходные места
    T temp, p;
 
    p = a[ N>>1 ];      // центральный элемент
 
    // процедура разделения
    do
    {
        while ( cmp(a[i],p) ) i++;
        while ( cmp(p,a[j]) ) j--;
 
        if (i <= j)
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }
    }
    while ( i<=j );
 
    // рекурсивные вызовы, если есть, что сортировать
    if ( j > 0 ) quickSortR(a, j);
    if ( N > i ) quickSortR(a+i, N-i);
}

(Тогда можно использовать не только функции, но и объекты, которые могут быть вызваны как функции).
А еще можно посмотреть объявление std::sort (например, http://www.sgi.com/tech/stl/sort.html).

Сообщение отредактировано: mo3r - 26.10.06, 11:20

mo3r
лучше и правда

Добавлено 26.10.06, 11:38
error C4519: default template arguments are only allowed on a class template

template<typename T, typename Comparer>
void quickSortR(vector<T>& a, Comparer cmp=std::less<T>())

bool SortByItem (const ITEM_DATA& elem1, const ITEM_DATA& elem2)

Добавлено 27.10.06, 07:18
P.S. const и & надо бы писать автоматически.

Какой тип у второго аргумента quickSortR при вызове?

Все, что то я совсем с ума сошел. Спасибо.

Вторая ошибка - на строчке, следующей за quickSortR(m_database, SortByItem);

template< typename BidirectionalIterator, typename Compare >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) {
    if( first != last ) {
        BidirectionalIterator left  = first;
        BidirectionalIterator right = last;
        BidirectionalIterator pivot = left++;
 
        while( left != right ) {
            if( cmp( *left, *pivot ) ) {
                ++left;
            } else {
                while( (left != --right) && cmp( *pivot, *right ) )
                    ;
                std::iter_swap( left, right );
            }
        }
 
        --left;
        std::iter_swap( first, left );
 
        quick_sort( first, left, cmp );
        quick_sort( right, last, cmp );
    }
}
 
template< typename BidirectionalIterator >
inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) {
    quick_sort( first, last,
        std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >()
        );
}