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

From: Michael Lacher (michael.lacher_at_[hidden])
Date: 2007-03-19 09:07:13

Sam Schetterer wrote:
> Hi. Since people want the sorting library to have something that the
> standard library sorts do not offer, I would like to know the most
> complicated sorting situations that user have encountered (like sort by
> name, and then first three digits of phone number, and if the sum of the
> first three digits of the phone number is less than 10, sort by the second 4
> digits of the phone number). I ask this because radixsort and radix
> quicksort are able to do those sorts, but I need input from users to add
> features. Also, even if you do not have any complicated sorts, ideas in
> general would help.
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
> 

Functionality that i would find useful (roughly sorted form most to 
least important):

* 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)

A complicated sort example i came across:

* The datatype is a struct of vectors of strings
* The criterium is the same dataype.
* sort according to how good the vectors of strings correlate in the 
list values and the criterium (many same values).

Another sort example from a different domain:

Take a set of points in 3d space. sort them (anti-)clockwise around a 
given point. sort them according to the length along a path. Both of 
these would need to associate a "sort value" with each point in a first 
pass to be able to sort efficient. This can be left to the user, but 
could also be handled by a library since the rest (establishing a 1-1 
relationship of "sort value" and actual value and sorting) is the same 
in each application.

regards,
Michael