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

From: Sam Schetterer (samthecppman_at_[hidden])
Date: 2007-03-22 18:22:06

On 3/22/07, Corrado Zoccolo <czoccolo_at_[hidden]> wrote:
>
> A trie data structure (http://en.wikipedia.org/wiki/Trie where the
> similarity with radix_sort is also drawn) is an associative data
> structure where the key is a (possibly of arbitrary lenght) sequence
> of fixed size objects (e.g. chars or ints). It is typically used to
> store strings, but as you extended the radixsort to operate on almost
> generic classes, the same can be achieved for trie.
>
> What I'm sayng is that if a class satisfies the requirement to be
> processed by radix_sort (let's say it defines an operator[] returning
> unsigned char), then that class can also be used as a key for a trie,
> so it is sound (and useful) for a library to provide both sorting and
> trie based implementations of set and map, for the classes that model
> the concept.
>
> On 3/22/07, Sam Schetterer < samthecppman_at_[hidden]> wrote:
> > On 3/21/07, Corrado Zoccolo <czoccolo_at_[hidden]> wrote:
> > >
> > > Hi Sam,
> > > I see sorting problems and sorted data structures as two faces of the
> > > same medal.
> > > In STL, for example, we have std::sort and std::set that both work
> > > with a two way comparison functor (std::less).
> > > I see a great potential in your work on operator[] with trie data
> > > structures.
> > > I think that an organic proposal of radix_sort with trie data
> > > structures (mimicking std::set and std::map), that both use the same
> > > operator[] approach would be very interesting.
> > >
> > > Corrado
> > > --

I think that the problem you are getting at is the type of tree created by
msd radix sort, which creates a bin for each possible byte value and then
puts corresponding bytes in the correct bin. However, that is not
implemented because for arrays of independent items, msd radix sort is
much less effecient than LSD radix sort. For arrays of arrays, multikey and
radix quicksort are faster than MSD sort because they avoid the problem of
empty bins.