Boost logo

Boost :

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


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

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.

Boost list run by bdawes at, gregod at, cpdaniel at, john at