Boost logo

Boost :

Subject: Re: [boost] Proposed templated integer_sort
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-01-14 17:27:57


Earlier I wrote:
> One of the things that your string sort does is to not compare
> known-equal initial substrings. Does anyone know if there is a variant
> of a conventional sort (e.g. quicksort) that does this?

I've had a quick play and come up with this:

     http://svn.chezphil.org/libpbe/trunk/include/string_qsort.hh

Of course the benefit depends on how many long common initial
substrings there are. Testing with the output of "find / -print" (i.e.
the pathnames of every file on my system, which will have lots of
common initial substrings) it is a bit slower than std::sort. So the
advantage of reducing the number of character comparisons [and that
reduction is substantial] does not make up for the absence of whatever
other cleverness std::sort does that I haven't replicated. But I
thought I'd post it anyway, in case anyone is interested or can see how
it could be improved.

Phil.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk