Re: [boost] Any interest in a sorting library with a multitude of sorts?

From: Paul Giaccone (paulg_at_[hidden])
Date: 2007-03-13 11:19:53

Sam Schetterer wrote:
> This sorting library would have quicksorts, radix quicksorts, 
> radixsorts, mergsorts, a sorted-array class, and an interface class to 
> be inherited from to allow sorting.

Most users, on finding they need to sort data, use something someone 
else has already written, such as the sort functions available in the 
STL. What could your library offer that this does not?

A couple of suggestions to answer my own question:

* Most programmers use quicksort without giving consideration to any 
other algorithms, because quicksort is often the best solution. It is 
not always best, of course: heap sort and merge sort are sometimes 
better (for example, if the data are already nearly sorted, merge sort 
might be better). An interesting feature that your library could provide 
would be a recommendation of which sort to use. I don't know if there is 
a criterion (short of actually doing the sort by various methods) that 
can be tested quickly to see which sort is likely to be fastest. You 
could see if the data is nearly in order (perhaps using a rank 
correlation) but this would not necessarily mean that a merge sort would 
be fastest.

A wish-list of ideas:

* Sorting into reverse order or forwards order
* Allowing the user to choose the "less-than" operator (as the STL sorts 
already do)
* A "sort by" function:

    class X
    {
        std::string name;
        int age;
        float height;
    }

    X array[10];

    //set members of elements of arrays here...

    sort_by(array, age);   //sorts the array by age

    //then, later on
    sort_by(array, height);

* A "sort within sort" function:

    sort_by(array, name, age);   //sort array by name, and then sort 
within name by age

giving:

    Fred, 23
    Fred, 31
    Jane, 34
    Joe, 18
    Julie, 29
    Julie, 43
    Kate, 51
    (etc)

so the names are in alphabetical order, and any duplicate entries with 
the same name are sorted within themselves by age.

This would be nestable to any depth, up to the number of members of the 
class that can be ordered, so you could also have:

    sort_by(array, name, height, age);

Just a few ideas.