Re: [boost] [sorting] What are the most complicated sorting problems?

From: Sam Schetterer (samthecppman_at_[hidden])
Date: 2007-03-19 10:36:58

Michael Lacher wrote:
>* provide an easy way to sort lists of pointers (without having to make
>a custom '<' operator each time).* Easy way to specify different
>comparison operators for various subfields. ie. in stead of one complex
>'<' operator, specify one for each subfield and then define sortorder
>(which subfield first, ...) on sorttime.
>* provide a good set of default '<' operators. at least:
>  - simple types (strings, numbers, ...)
>  - pointers to simple types
>  - pairs of the above
>* Specify ascending vs. descending sorting. Trivial criteria really, but
>reduces complexity (or number) of the '<' operators.
>* return the n highest/lowest only. (optimized, ie: not full sort and
>then cutting solution)
First, to sort a list of pointers, they already have operator< defined, as
they are a built in type. If the keys were pointers to arrays, then that
problem can be solved by multikey wuicksoprt, which I am currently writing,
which is a mix of quicksort and radixsort that works on keys that are arrays
or vectors. Then, to specify various operator<s for different fields, you
would use normal radix sort, (not using operator<,.but a byte extraction
function) and you would start with the least significant field using the
varaible bit radixsort, sort only using it, and pass the byte extraction the
function. Then you would sort by the second least significant subfield, and
pass whatever byte extraction function you wanted. However, to make that
process much more simple, I will implement a version of radixsort and radix
quicksort that  allows you to pass more than one function(you will still hve
to do a little bit of extra work).