Re: [boost] [sorting] Is there still interest?

21 Mar 2007

      Sam Schetterer wrote:
...
Hi. I am just wondering if there is still interest in the library, because
I have not recieved any comments on the library in the last two days, no
posts at all, while I have made multiple posts, some with very important
ideas in them.
Hi Sam,

I downloaded your library to do some testing.  The first issue I ran 
into was that MSVC 7.1 complained about some of the specializations:
template<>
void insertion<char*>(typename std::deque<char*>::iterator& a, int l, int r)
and
template<>
void r_insertion<char*>(typename std::deque<char*>::iterator& a, int l, 
int r)
(This may be a vc 7.1 bug, I'm not sure.)

The second issue is that in rquicksort.hpp (and possibly other places), 
a lot of the functions have parameters named 'strfnc', but the functions 
use parameters named 'strfunc'.

The final issue is that create_id_string has some bugs.  (It only works 
if %s is the first control sequence it encounters, so format strings 
like "%e" will crash.)

After fixing those issues, I found that the radix_qsort and radix_sort 
are slower than standard sort.  Maybe this is a result of when I 
commented out the specializations of insertion and r_insertion?

I've attached the changes I made to the sorting stuff to get it to 
compile and run on MSVC 7.1.  I've also included the code that I used to 
get the timings.  (I know that timings are difficult to get, and I 
welcome any comments/criticisms.  Perhaps my results are bad because I 
ended up sorting an already sorted array.  However, all of the sorts 
were fast enough that I had to do this to a non-zero number.)

Here are my results:
radix_sort: people = 0.94s, radixtest = 0.12s
radix_qsort: people = 0.69s, radixtest = 2.4s
std::sort: people = 0.037s, radixtest = 0.015s

Specs: Windows XP Professional x64 SP2, Visual C++ 7.1, Intel Xeon dual 
core @ 2.66GHz, 2.0 GB RAM.

Do you have anything that shows that your code beats std::sort?

David

//include file for radix quicksort
#ifndef BOOST_RQUICKSORT_HPP
#define BOOST_RQUICKSORT_HPP
#include <cstring>
#include <cstdlib>
#include "detail/insertion.hpp"
#include <stdarg.h>
namespace boost
{
	namespace detail
	{
        template<class T>
        inline unsigned char qdigit(const T& a, int d)
        {
            return a.idstring_qs[d];
        }
        typedef char* cptr;
        template<>
        inline unsigned char qdigit<cptr>(const cptr& a, int d)
        {
            return a[d];
        }
        template<class T>
        void rquicksort(T* ar, int l, int r, int bit)
        {
            if((r - l) <= 16) { insertion(ar, l, r); return;}
            register T* a = ar;
            register int i = l - 1, j = r, d = bit, v = qdigit(a[j], d);//speed increase with registers
            int p = i, q = j;
            while(i < j)
            {
                while(qdigit(a[++i], d) < v) ;
                while(v < qdigit(a[--j], d)) if(j == l) break;
                if(i > j) break;
                std::swap(a[i], a[j]);
                if(qdigit(a[i], d) == v) {++p; std::swap(a[p], a[i]);}
                if(qdigit(a[j], d) == v) {--q; std::swap(a[q], a[j]);}
            }
            if(p == q)
            {
                 if(v != '\0') rquicksort(a, l, r, d + 1);
                 return;
            }
            if(qdigit(a[i], d) < v) ++i;
            int k = l;
            for( ; k <= p; j--, k++) std::swap(a[k], a[j]);
            for(k = r; k >= q; i++, k--) std::swap(a[k], a[i]);
            rquicksort(a, l, j, d);
            if((i == r) && (qdigit(a[i], d) == v)) ++i;
            if(v != '\0') rquicksort(a, j + 1, i - 1, d + 1);
            rquicksort(a, i, r, d);
        }
        template<class T>
        void rrquicksort(T* ar, int l, int r, int bit)
        {
            if((r - l) <= 16) { r_insertion(ar, l, r); return;}
            register T* a = ar;
            register int i = l - 1, j = r, d = bit, v = qdigit(a[j], d);//speed increase with registers
            int p = i, q = j;
            while(i < j)
            {
                while(v < qdigit(a[++i], d)) ;
                while(qdigit(a[--j], d) < v) if(j == l) break;
                if(i > j) break;
                std::swap(a[i], a[j]);
                if(qdigit(a[i], d) == v) {++p; std::swap(a[p], a[i]);}
                if(qdigit(a[j], d) == v) {--q; std::swap(a[q], a[j]);}
            }
            if(p == q)
            {
                 if(v != '\0') rrquicksort(a, l, r, d + 1);
                 return;
            }
            if(v < qdigit(a[i], d)) ++i;
            int k = l;
            for( ; k <= p; j--, k++) std::swap(a[k], a[j]);
            for(k = r; k >= q; i++, k--) std::swap(a[k], a[i]);
            rrquicksort(a, l, j, d);
            if((i == r) && (qdigit(a[i], d) == v)) ++i;
            if(v != '\0') rrquicksort(a, j + 1, i - 1, d + 1);
            rrquicksort(a, i, r, d);
        }
    }
	template<class T>
	inline void radix_qsort(T* data, int size) //normal
	{
		detail::rquicksort(data, 0, size, 0);
	}
    template<class T>
    inline void r_radix_qsort(T* data, int size) //reverse
    {
        detail::rrquicksort(data, 0, size, 0);
    }
    /////////////////////////user-defined functions
    namespace detail
	{
        template<class T>
        void rquicksort(T* ar, int l, int r, int bit, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&))
        {
            if((r - l) <= 16) { insertion(ar, l, r, ltfunc); return;}
            register T* a = ar;
            register int i = l - 1, j = r, d = bit, v = strfunc(a[j], d);
            int p = i, q = j;
            while(i < j)
            {
                while(strfunc(a[++i], d) < v) ;
                while(v < strfunc(a[--j], d)) if(j == l) break;
                if(i > j) break;
                std::swap(a[i], a[j]);
                if(strfunc(a[i], d) == v) {++p; std::swap(a[p], a[i]);}
                if(strfunc(a[j], d) == v) {--q; std::swap(a[q], a[j]);}
            }
            if(p == q)
            {
                 if(v != '\0') rquicksort(a, l, r, d + 1);
                 return;
            }
            if(strfunc(a[i], d) < v) ++i;
            int k = l;
            for( ; k <= p; j--, k++) std::swap(a[k], a[j]);
            for(k = r; k >= q; i++, k--) std::swap(a[k], a[i]);
            rquicksort(a, l, j, d);
            if((i == r) && (strfunc(a[i], d) == v)) ++i;
            if(v != '\0') rquicksort(a, j + 1, i - 1, d + 1);
            rquicksort(a, i, r, d);
        }
        template<class T>
        void rrquicksort(T* ar, int l, int r, int bit, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&))
        {
            if((r - l) <= 16) { r_insertion(ar, l, r, ltfunc); return;}
            register T* a = ar;
            register int i = l - 1, j = r, d = bit, v = strfunc(a[j], d);//speed increase with registers
            int p = i, q = j;
            while(i < j)
            {
                while(v < strfunc(a[++i], d)) ;
                while(strfunc(a[--j], d) < v) if(j == l) break;
                if(i > j) break;
                std::swap(a[i], a[j]);
                if(strfunc(a[i], d) == v) {++p; std::swap(a[p], a[i]);}
                if(strfunc(a[j], d) == v) {--q; std::swap(a[q], a[j]);}
            }
            if(p == q)
            {
                 if(v != '\0') rrquicksort(a, l, r, d + 1);
                 return;
            }
            if(v < strfunc(a[i], d)) ++i;
            int k = l;
            for( ; k <= p; j--, k++) std::swap(a[k], a[j]);
            for(k = r; k >= q; i++, k--) std::swap(a[k], a[i]);
            rrquicksort(a, l, j, d);
            if((i == r) && (strfunc(a[i], d) == v)) ++i;
            if(v != '\0') rrquicksort(a, j + 1, i - 1, d + 1);
            rrquicksort(a, i, r, d);
        }
    }
	template<class T>
	inline void radix_qsort(T* data, int size, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&)) //normal
	{
		detail::rquicksort(data, 0, size, 0, strfunc, ltfunc);
	}
    template<class T>
    inline void r_radix_qsort(T* data, int size, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&)) //reverse
    {
        detail::rrquicksort(data, 0, size, 0, strfunc, ltfunc);
    }
    //////////////////////////////////////////////////////////////////////////variable bytes
    template<class T>
    inline void radix_qsort(T* a, int size, int startbyte)
    {
        detail::rquicksort(a, 0, size, startbyte);
    }
    template<class T>
    inline void radix_qsort(T* a, int start, int size, int startbyte)
    {
        detail::rquicksort(a, start, size, startbyte);
    }
    template<class T>
    inline void radix_qsort(T* a, int size, int startbyte, unsigned char(*strfunc)(const T&, int d), bool(*ltfunc)(const T&, const T&))
    {
        detail::rquicksort(a, 0, size, startbyte, strfunc, ltfunc);
    }
    template<class T>
    inline void radix_qsort(T* a, int start, int size, int startbyte, unsigned char(*strfunc)(const T&, int d), bool(*ltfunc)(const T&, const T&))
    {
        detail::rquicksort(a, start, size, startbyte, strfunc, ltfunc);
    }
    ////////////////////////////////////////////////////////////stl iterator
    namespace detail
	{
        template<class T>
        void rquicksort(typename std::deque<T>::iterator& a, int l, int r, int bit)
        {
            if((r - l) <= 16) { insertion<T>(a, l, r); return;}
            register int i = l - 1, j = r, d = bit, v = qdigit(*(a + j), d);//speed increase with registers
            int p = i, q = j;
            while(i < j)
            {
                while(qdigit(*(a + ++i), d) < v) ;
                while(v < qdigit(*(a + --j), d)) if(j == l) break;
                if(i > j) break;
                std::swap(*(a + i), *(a + j));
                if(qdigit(*(a + i), d) == v) {++p; std::swap(*(a + p), *(a + i));}
                if(qdigit(*(a + j), d) == v) {--q; std::swap(*(a + q), *(a + j));}
            }
            if(p == q)
            {
                 if(v != '\0') rquicksort<T>(a, l, r, d + 1);
                 return;
            }
            if(qdigit(*(a + i), d) < v) ++i;
            int k = l;
            for( ; k <= p; j--, k++) std::swap(*(a + k), *(a + j));
            for(k = r; k >= q; i++, k--) std::swap(*(a + k), *(a + i));
            rquicksort<T>(a, l, j, d);
            if((i == r) && (qdigit(*(a + i), d) == v)) ++i;
            if(v != '\0') rquicksort<T>(a, j + 1, i - 1, d + 1);
            rquicksort<T>(a, i, r, d);
        }
        template<class T>
        void rrquicksort(typename std::deque<T>::iterator& a, int l, int r, int bit)
        {
            if((r - l) <= 16) { r_insertion<T>(a, l, r); return;}
            register int i = l - 1, j = r, d = bit, v = qdigit(*(a + j), d);//speed increase with registers
            int p = i, q = j;
            while(i < j)
            {
                while(v < qdigit(*(a + ++i), d)) ;
                while(qdigit(*(a + --j), d) < v) if(j == l) break;
                if(i > j) break;
                std::swap(*(a + i), *(a + j));
                if(qdigit(*(a + i), d) == v) {++p; std::swap(*(a + p), *(a + i));}
                if(qdigit(*(a + j), d) == v) {--q; std::swap(*(a + q), *(a + j));}
            }
            if(p == q)
            {
                 if(v != '\0') rrquicksort<T>(a, l, r, d + 1);
                 return;
            }
            if(v < qdigit(*(a + i), d)) ++i;
            int k = l;
            for( ; k <= p; j--, k++) std::swap(*(a + k), *(a + j));
            for(k = r; k >= q; i++, k--) std::swap(*(a + k), *(a + i));
            rrquicksort<T>(a, l, j, d);
            if((i == r) && (qdigit(*(a + i), d) == v)) ++i;
            if(v != '\0') rrquicksort<T>(a, j + 1, i - 1, d + 1);
            rrquicksort<T>(a, i, r, d);
        }
    }
	template<class T>
	inline void radix_qsort(typename std::deque<T>::iterator& data, int size) //normal
	{
		detail::rquicksort<T>(data, 0, size, 0);
	}
    template<class T>
    inline void r_radix_qsort(typename std::deque<T>::iterator& data, int size) //reverse
    {
        detail::rrquicksort<T>(data, 0, size, 0);
    }
    /////////////////////////user-defined functions
    namespace detail
	{
        template<class T>
        void rquicksort(typename std::deque<T>::iterator& a, int l, int r, int bit, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&))
        {
            if((r - l) <= 16) { insertion<T>(a, l, r, ltfunc); return;}
            register int i = l - 1, j = r, d = bit, v = strfunc(*(a + j), d);
            int p = i, q = j;
            while(i < j)
            {
                while(strfunc(*(a + ++i), d) < v) ;
                while(v < strfunc(*(a + --j), d)) if(j == l) break;
                if(i > j) break;
                std::swap(*(a + i), *(a + j));
                if(strfunc(*(a + i), d) == v) {++p; std::swap(*(a + p), *(a + i));}
                if(strfunc(*(a + j), d) == v) {--q; std::swap(*(a + q), *(a + j));}
            }
            if(p == q)
            {
                 if(v != '\0') rquicksort<T>(a, l, r, d + 1);
                 return;
            }
            if(strfunc(*(a + i), d) < v) ++i;
            int k = l;
            for( ; k <= p; j--, k++) std::swap(*(a + k), *(a + j));
            for(k = r; k >= q; i++, k--) std::swap(*(a + k), *(a + i));
            rquicksort<T>(a, l, j, d);
            if((i == r) && (strfunc(*(a + i), d) == v)) ++i;
            if(v != '\0') rquicksort<T>(a, j + 1, i - 1, d + 1);
            rquicksort<T>(a, i, r, d);
        }
        template<class T>
        void rrquicksort(typename std::deque<T>::iterator& a, int l, int r, int bit, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&))
        {
            if((r - l) <= 16) { r_insertion<T>(a, l, r, ltfunc); return;}
            register int i = l - 1, j = r, d = bit, v = strfunc(*(a + j), d);//speed increase with registers
            int p = i, q = j;
            while(i < j)
            {
                while(v < strfunc(*(a + ++i), d)) ;
                while(strfunc(*(a + --j), d) < v) if(j == l) break;
                if(i > j) break;
                std::swap(*(a + i), *(a + j));
                if(strfunc(*(a + i), d) == v) {++p; std::swap(*(a + p), *(a + i));}
                if(strfunc(*(a + j), d) == v) {--q; std::swap(*(a + q), *(a + j));}
            }
            if(p == q)
            {
                 if(v != '\0') rrquicksort<T>(a, l, r, d + 1);
                 return;
            }
            if(v < strfunc(*(a + i), d)) ++i;
            int k = l;
            for( ; k <= p; j--, k++) std::swap(*(a + k), *(a + j));
            for(k = r; k >= q; i++, k--) std::swap(*(a + k), *(a + i));
            rrquicksort<T>(a, l, j, d);
            if((i == r) && (strfunc(*(a + i), d) == v)) ++i;
            if(v != '\0') rrquicksort<T>(a, j + 1, i - 1, d + 1);
            rrquicksort<T>(a, i, r, d);
        }
    }
	template<class T>
	inline void radix_qsort(typename std::deque<T>::iterator& data, int size, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&)) //normal
	{
		detail::rquicksort<T>(data, 0, size, 0, strfunc, ltfunc);
	}
    template<class T>
    inline void r_radix_qsort(typename std::deque<T>::iterator& data, int size, unsigned char (*strfunc)(const T&, int), bool(*ltfunc)(const T&, const T&)) //reverse
    {
        detail::rrquicksort<T>(data, 0, size, 0, strfunc, ltfunc);
    }
    //////////////////////////////////////////////////////////////////////////variable bytes
    template<class T>
    inline void radix_qsort(typename std::deque<T>::iterator& a, int size, int startbyte)
    {
        detail::rquicksort<T>(a, 0, size, startbyte);
    }
    template<class T>
    inline void radix_qsort(typename std::deque<T>::iterator& a, int start, int size, int startbyte)
    {
        detail::rquicksort<T>(a, start, size, startbyte);
    }
     template<class T>
    inline void radix_qsort(typename std::deque<T>::iterator& a, int size, int startbyte, unsigned char(*strfunc)(const T&, int d), bool(*ltfunc)(const T&, const T&))
    {
        detail::rquicksort<T>(a, 0, size, startbyte, strfunc, ltfunc);
    }
    template<class T>
    inline void radix_qsort(typename std::deque<T>::iterator& a, int start, int size, int startbyte, unsigned char(*strfunc)(const T&, int d), bool(*ltfunc)(const T&, const T&))
    {
        detail::rquicksort<T>(a, start, size, startbyte, strfunc, ltfunc);
    }
    std::size_t create_id_string(const char* fmt, char* dest, ...)
    {
        va_list ap;
        const char* p;
        std::size_t n = 0;
        va_start(ap, dest);
        for(p = fmt; *p; p++)
        {
            if(*p != '%')
            {
                dest[n++] = *p;
                continue;
            }
            switch(*++p)
            {
                case 'd': case 'D': case 'i': case 'I':
                {
                    int itemp = va_arg(ap, int);
                    _ui64toa(itemp, (char*)(dest+n), 16);
                    n += strlen(dest+n);
                    break;
                }
                case 's': case 'S':
                {
                    const char *ctemp = va_arg(ap, const char*);
                    strcpy(dest+n, ctemp);
                    n += strlen(dest+n);
                    break;
                }
                case 'e': case 'E': case 'g': case 'G':
                {
                    double dtemp = va_arg(ap, double);
                    long long dval = *((long long*)&dtemp);
                    _ui64toa(dval, (char*)(dest+n), 16);
                    n += strlen(dest+n);
                    break;
                }
                default:
                {
                    dest[n++] = *p;
                    break;
                }
            }
        }
        dest[n++] = '\0';
        va_end(ap);
        return n + 1; //1 compenstates for zero index array
    }
}
#endif

#ifndef BOOST_DETAIL_INSERTION_HPP
#define BOOST_DETAIL_INSERTION_HPP
#include <algorithm>
#include <cstring>
#include <deque>
namespace boost
{
namespace detail
{
template<class T>
void insertion(T* ar, int l, int r)
{
	register T* a = ar;
	register int i;
	for(i = r; i > l; i--) if(a[i] < a[i - 1]) std::swap<T>(a[i], a[i - 1]);
	for(i = l + 2; i <= r; i++)
	{
		register int j = i; T v = a[i];
		while(v < a[j - 1])
		{
			a[j] = a[j - 1];
			--j;
		}
		a[j] = v;
	}
}

template<>
void insertion<char*>(char** ar, int l, int r)
{
	register char** a = ar;
	register int i;
	for(i = r; i > l; i--) if(strcmp(a[i], a[i - 1]) & 0x80000000) std::swap<char*>(a[i], a[i - 1]);
	for(i = l + 2; i <= r; i++)
	{
		register int j = i; register char* v = a[i];
		while(strcmp(v, a[j - 1]) & 0x80000000)
		{
			a[j] = a[j - 1];
			--j;
		}
		a[j] = v;
	}
}
template<class T>
void r_insertion(T* ar, int l, int r)
{
	register T* a = ar;
	register int i;
	for(i = r; i > l; i--) if(a[i - 1] <  a[i]) std::swap<T>(a[i], a[i - 1]);
	for(i = l + 2; i <= r; i++)
	{
		register int j = i; T v = a[i];
		while(a[j - 1] < v)
		{
			a[j] = a[j - 1];
			--j;
		}
		a[j] = v;
	}
}
template<>
void r_insertion<char*>(char** ar, int l, int r)
{
	register char** a = ar;
	register int i;
	for(i = r; i > l; i--) if(strcmp(a[i - 1], a[i]) & 0x80000000) std::swap<char*>(a[i], a[i - 1]);
	for(i = l + 2; i <= r; i++)
	{
		register int j = i; char* v = a[i];
		while(strcmp(a[j - 1], v) & 0x80000000)
		{
			a[j] = a[j - 1];
			--j;
		}
		a[j] = v;
	}
}
//////////////user-defined
template<class T>
void insertion(T* ar, int l, int r, bool(*ltfunc)(const T&, const T&))
{
	register T* a = ar;
	register int i;
	for(i = r; i > l; i--) if(lt(a[i], a[i - 1])) std::swap<T>(a[i], a[i - 1]);
	for(i = l + 2; i <= r; i++)
	{
		register int j = i; T v = a[i];
		while(lt(v, a[j - 1]))
		{
			a[j] = a[j - 1];
			--j;
		}
		a[j] = v;
	}
}
template<class T>
void r_insertion(T* ar, int l, int r, bool(*ltfunc)(const T&, const T&))
{
	register T* a = ar;
	register int i;
	for(i = r; i > l; i--) if(lt(a[i - 1], a[i])) std::swap<T>(a[i], a[i - 1]);
	for(i = l + 2; i <= r; i++)
	{
		register int j = i; T v = a[i];
		while(lt(a[j - 1], v))
		{
			a[j] = a[j - 1];
			--j;
		}
		a[j] = v;
	}
}
///////////////////////////////////////////////////////////////////////standard library sorters
template<class T>
void insertion(typename std::deque<T>::iterator& a, int l, int r)
{
	register int i;
	for(i = r; i > l; i--) if(*(a + i) < *(a + i - 1)) std::swap<T>(*(a + i), *(a + i - 1));
	for(i = l + 2; i <= r; i++)
	{
		register int j = i; T v = *(a + i);
		while(v < *(a + j - 1))
		{
			*(a + j) = *(a + j - 1);
			--j;
		}
		*(a + j) = v;
	}
}

//template<>
//void insertion<char*>(typename std::deque<char*>::iterator& a, int l, int r)
//{
//	register int i;
//	for(i = r; i > l; i--) if(strcmp(*(a + i), *(a + i - 1)) & 0x80000000) std::swap<char*>(*(a + i), *(a + i - 1));
//	for(i = l + 2; i <= r; i++)
//	{
//		register int j = i; register char* v = *(a + i);
//		while(strcmp(v, *(a + j - 1)) & 0x80000000)
//		{
//			*(a + j) = *(a + j - 1);
//			--j;
//		}
//		*(a + j) = v;
//	}
//}
template<class T>
void r_insertion(typename std::deque<T>::iterator& a, int l, int r)
{
	register int i;
	for(i = r; i > l; i--) if(*(a + i - 1) <  *(a + i)) std::swap<T>(*(a + i), *(a + i - 1));
	for(i = l + 2; i <= r; i++)
	{
		register int j = i; T v = *(a + i);
		while(*(a + j - 1) < v)
		{
			*(a + j) = *(a + j - 1);
			--j;
		}
		*(a + j) = v;
	}
}
//template<>
//void r_insertion<char*>(typename std::deque<char*>::iterator& a, int l, int r)
//{
//	register int i;
//	for(i = r; i > l; i--) if(strcmp(*(a + i - 1), *(a + i)) & 0x80000000) std::swap<char*>(*(a + i), *(a + i - 1));
//	for(i = l + 2; i <= r; i++)
//	{
//		register int j = i; char* v = *(a + i);
//		while(strcmp(*(a + j - 1), v) & 0x80000000)
//		{
//			*(a + j) = *(a + j - 1);
//			--j;
//		}
//		*(a + j) = v;
//	}
//}
//////////////user-defined
template<class T>
void insertion(typename std::deque<T>::iterator& a, int l, int r, bool(*ltfunc)(const T&, const T&))
{
	register int i;
	for(i = r; i > l; i--) if(lt(*(a + i), *(a + i - 1))) std::swap<T>(*(a + i), *(a + i - 1));
	for(i = l + 2; i <= r; i++)
	{
		register int j = i; T v = *(a + i);
		while(lt(v, *(a + j - 1)))
		{
			*(a + j) = *(a + j - 1);
			--j;
		}
		*(a + j) = v;
	}
}
template<class T>
void r_insertion(typename std::deque<T>::iterator& a, int l, int r, bool(*ltfunc)(const T&, const T&))
{
	register int i;
	for(i = r; i > l; i--) if(lt(*(a + i - 1), *(a + i))) std::swap<T>(*(a + i), *(a + i - 1));
	for(i = l + 2; i <= r; i++)
	{
		register int j = i; T v = *(a + i);
		while(lt(*(a + j - 1), v))
		{
			*(a + j) = *(a + j - 1);
			--j;
		}
		*(a + j) = v;
	}
}
}
}
#endif

#include <iostream>
#include <string>
#include <vector>

#include <ctime>

#define STD_SORT     0
#define RADIX_Q_SORT 1
#define RADIX_SORT   2

// --------------------------------------
// TODO: Set SORT_TYPE to one of:
// STD_SORT, RADIX_Q_SORT, or RADIX_SORT
// --------------------------------------
#define SORT_TYPE RADIX_SORT

#if (SORT_TYPE == RADIX_Q_SORT)
#include <boost/sorting/rquicksort.hpp>
#elif (SORT_TYPE == RADIX_SORT)
#include <boost/sorting/radix.hpp>
#include <boost/sorting/rquicksort.hpp> // for create_id_string
#else // std::sort
#include <algorithm>
#endif

static double doublerand()
{
    double a = static_cast<double>(rand());
    double b = static_cast<double>(rand());
    double c = static_cast<double>(rand());
    return (a*b)/c;
}

static std::string stringrand()
{
    std::string s;
    for(int i=0 ; i<5 ; ++i)
    {
        s += static_cast<char>(rand() % 26) + 'a';
    }
    return s;
}

static int intrand() {return rand();}

struct person
{
    std::string name;
    int iNum;
    double fNum;
    int order;

#if ((SORT_TYPE == RADIX_Q_SORT) || (SORT_TYPE == RADIX_SORT))
    static const int STR_SZ = 30;
    char idstring_qs[STR_SZ]; 
#endif

    person(){}
    person(int iOrder, int inum, const std::string &n, double w)
    {
        order = iOrder;
        iNum = inum;
        name = n;
        fNum = w;

#if ((SORT_TYPE == RADIX_Q_SORT) || (SORT_TYPE == RADIX_SORT))
        //%s means string, %d means int, and %e means double
        boost::create_id_string("%s%e%d", idstring_qs, name.c_str(), fNum, iNum);
#endif
    }

#if (SORT_TYPE == RADIX_Q_SORT)
    inline int operator<(const person& rhs) const
    {
        return strcmp(idstring_qs, rhs.idstring_qs) & 0x80000000;
    }
#elif (SORT_TYPE == RADIX_SORT)
    inline unsigned char operator[](int d) const
    {
        return idstring_qs[d];
    }
#else // std::sort
    inline bool operator<(const person& rhs)
    {
        if(name < rhs.name) return true;
        if(rhs.name < name) return false;

        if(fNum < rhs.fNum) return true;
        if(rhs.fNum < fNum) return false;

        return (iNum < rhs.iNum);
    }
#endif
};

static void FillData(std::vector<double> &vec_d, std::vector<int> &vec_i, 
                     std::vector<std::string> &vec_s, std::size_t desired_size)
{
    vec_d.clear(); vec_d.reserve(desired_size);
    vec_i.clear(); vec_i.reserve(desired_size);
    vec_s.clear(); vec_s.reserve(desired_size);

    for(std::size_t i=0 ; i<desired_size ; ++i)
    {
        vec_d.push_back(doublerand());
        vec_i.push_back(intrand());
        vec_s.push_back(stringrand());
    }
}

// We want a large number of objects to sort, but we don't
// want it to crash if it can't find enough stack space.
static const std::size_t NUM_PEOPLE = 10000;

static void PrintPeople(const person people[NUM_PEOPLE])
{
    for(int x = 0; x < NUM_PEOPLE; x++)
    {
        std::cout << people[x].name 
            << " has floating point value " << people[x].fNum  
            << " and is #" << people[x].iNum 
            << " originally " << people[x].order
            << std::endl;
    }
}

static int GetMin(int a, int b) {return (std::min)(a,b);}
static int GetMax(int a, int b, int c) {return (std::max)(a, (std::max)(b,c));}

static clock_t TestPeopleSorting(int num_loops)
{
    static const int I_MOD = 5;
    static const int S_MOD = 7;
    static const int F_MOD = 3;

    //// If I make all objects unique (with the code below), then the 
    //// sorts are closer, but std::sort still wins.
    //static const int I_MOD = NUM_PEOPLE;
    //static const int S_MOD = NUM_PEOPLE;
    //static const int F_MOD = NUM_PEOPLE;

    static const int DATA_MAX = GetMin(NUM_PEOPLE, GetMax(I_MOD, S_MOD, F_MOD));

    std::vector<double> fnumbers;
    std::vector<int> numbers;
    std::vector<std::string> names;

    FillData(fnumbers, numbers, names, DATA_MAX);

    person people[NUM_PEOPLE];
    for(int x = 0; x < NUM_PEOPLE; x++)
    {
        people[x] = person(x, numbers[x%I_MOD], names[x%S_MOD], fnumbers[x%F_MOD]);
    }

    //std::cout << "Before sort:\n";
    //PrintPeople(people);

	std::clock_t start_time = std::clock();
    for(int i=0 ; i<num_loops ; ++i)
    {
#if (SORT_TYPE == RADIX_Q_SORT)
        boost::radix_qsort(people, NUM_PEOPLE-1); // why -1 ???
#elif (SORT_TYPE == RADIX_SORT)
        boost::radix_sort(people, NUM_PEOPLE);
#else // std::sort
        std::sort(people, people+NUM_PEOPLE);
#endif
    }
    std::clock_t end_time = std::clock();

    //std::cout << "\n\nAfter sort:\n";
    //PrintPeople(people);

    return end_time - start_time;
}

class radixtest
{
public:
    int numbers[2];
#if (SORT_TYPE == RADIX_Q_SORT)
    static const int STR_SZ = 30;
    char idstring_qs[STR_SZ]; 
#endif
    radixtest()
    {
        numbers[0] = rand() % 10;
        numbers[1] = rand() % 10;
#if (SORT_TYPE == RADIX_Q_SORT)
        //%s means string, %d means int, and %e means double
        boost::create_id_string("%e%e", idstring_qs, numbers[0], numbers[1]);
#endif
    }
    inline unsigned char operator[](int num)
    {return ((unsigned char*)numbers)[num];}
    inline unsigned char operator[](int num) const
    {return ((unsigned char*)numbers)[num];}
    ~radixtest()
    {}
#if ((SORT_TYPE == STD_SORT) || (SORT_TYPE == RADIX_Q_SORT))
    bool operator<(const radixtest& a) const
    {
        if(numbers[0] < a.numbers[0])
        return true;
        else if(numbers[0] == a.numbers[0])
        {
            if (numbers[1] < a.numbers[1])
                return true;
        }
        return false;
    }
#endif
};

// We want a large number of objects to sort, but we don't
// want it to crash if it can't find enough stack space.
static const int NUM_RADIX = 15000;

static clock_t TestRadixSorting(int num_loops)
{
    radixtest tests[NUM_RADIX];
	std::clock_t start_time = std::clock();
    for(int i=0 ; i<num_loops ; ++i)
    {
#if (SORT_TYPE == RADIX_Q_SORT)
        boost::radix_qsort(tests, NUM_RADIX-1); // why -1 ???
#elif (SORT_TYPE == RADIX_SORT)
        boost::radix_sort(tests, NUM_RADIX, sizeof(int)*2);
#else // std::sort
        std::sort(tests, tests+NUM_RADIX);
#endif
    }
    std::clock_t end_time = std::clock();

    return end_time - start_time;
}

int main(int argc, char* argv[])
{
    //clock_t people_sorting = TestPeopleSorting(10);
    //clock_t radix_sorting = TestRadixSorting(100);
    clock_t people_sorting = TestPeopleSorting(1);
    clock_t radix_sorting = TestRadixSorting(1);

    std::cout << "\nTime for "
#if (SORT_TYPE == RADIX_Q_SORT)
        << "radix_qsort "
#elif (SORT_TYPE == RADIX_SORT)
        << "radix_sort "
#else
        << "std::sort "
#endif
        << "sorting:\n"
        << "people:    " << static_cast<double>(people_sorting) / CLOCKS_PER_SEC << std::endl
        << "radixtest: " << static_cast<double>(radix_sorting) / CLOCKS_PER_SEC << std::endl;

    return 0;
}

Re: [boost] [sorting] Is there still interest?

David Walthall