Re: [boost] Proposed templated integer_sort

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2008-06-30 16:45:47

Hi Steven,

I've had time to have a quick look at your code:

Steven Ross wrote:
> You are correct, I do require a comparison operator too (<).  I assumed that,
> but it's good to make clear.

> I could sort fixed-point data, given a >> operator, which you should be able
> to implement.  Here is what is needed for a hybrid MSB radix sort and 
> introsort combo:
>
> bool operator <(const T &) : for comparison
> size_t operator -(const T & lhs, const T & rhs) : a - b > 0 -> b > a
> Note: - will always be used such that lhs >= rhs inside the algorithm.
> T operator >>(const T &) : to divide the values in a quick and efficient
> manner that will preserve ordering (a >> n) < (b >> n) -> a < b.  

No, T T::operator>>(const T&) isn't what you're using; you need int 
T::operator>>(int).  The shift amount is obviously an integer, not T, 
but furthermore you're using the result of the shift as a bin number.  
So if my fixed-point class lets you say e.g. assert(3.1415 >> 2 == 
0.7854), i.e. it returns a T, then you can't use that to select a bin.

My fixed class provides a base() method to access the underlying 
integer type, and somehow your algorithm needs to be supplied with a 
functor that uses that base() method to extract the next few bits.  I'm 
not sure how best to do that: it's easy to solve for specific cases but 
it's hard to be general without becoming so generic that the code is incomprehensible.

You can draw parallels with generating CRCs or hash functions for 
arbitrary types [i.e. what tr1:: hash functions don't do]: you need a 
simple concept that most types can satisfy for accessing their bit 
patterns.  In your case you also need that you get the bit patterns 
with some sort of most-to-least significant ordering.

Anyway, I suggest that you get it looking good for integers first and 
then we can all think about how to make it more generic.  You might 
also like to prepare some benchmarks so that we can see how fast it 
really is and argue about the distribution of the values being sorted.  
I have a nice big file of GPS coordinates you can try it on...

Oh, since no-one else has mentioned it, there was someone else who 
proposed some sorting algorithms here a while ago.  You might like to 
have a look at the list archive (search for "sorting library") and see 
what you can learn.

Phil.