Modern C++ compliant selection sort

Question

I am writing, as review, Modern C++ compliant versions of sorting algorithms I previously have seen. This post is about selection sort, and selection sort only.

Whilst selection sort is rather simple, straightforward, and not the best in terms of performance, I wanted to know if there were any ways to improve upon my implementation, especially in terms of performance:

// Orders a list of values by repeatedly putting the smallest
// or largest unplaced value into its final position.
template<typename T>
void sort_selection(std::vector<T> & arr)
{
    std::vector<T>::iterator min, beg, end = arr.end();
    for (beg = arr.begin(); beg < end; ++beg)
    {
        min = std::min_element(beg, end);
        if (*min < *beg)
            std::iter_swap(min, beg);
    }
}

I'm using local variables min, beg, end outside the loop to lower the amount of dereferencing and stack allocations and take advantage of temporal locality. Also I am using iterators and min_element, iter_swap to be modern c++ compliant.

Answer 1

There's not really much code here to review, and for what it is, all I really have are some subjective stylistic concerns (I'm not a fan of omitted braces or multiple declarations per line). Instead of reviewing it as a stand alone snippet, I'm going to review it as what I would expect a fully idiomatic and generic sorting function to be in C++.

---

The biggest issue I see with this is that it's not quite up to snuff with regards to C++ idioms. It's very rare to write a method that actually takes a container (and isn't just a convenience method for the iterator version). Instead, it's customary to take two iterators since that allows you to operate on any container. In certain situations, you can even make decisions based on the iterator type. For example, you could have your sort fall back to std::sort if the iterator is a random access iterator.

Anyway, what I'd expect to see is this:

template<typename FwdIterator>
void sort_selection(FwdIterator beg, FwdIterator end)
{
    ...
}

Some people prefer just Iter or something similar, but I like to specify the lowest iterator requirement necessary to use the function. In this case, you just require a forward iterator.

---

Speaking of iterator types, you should use != over < when dealing with iterator loops if all you care about is whether or not the second iterator has been reached by the first.

operator< might not be present on iterators in situations where operator!= is. This is a perfect example actually. Forward iterators are not required to define operator< and in fact usually won't. Other than the std::vector hard coding, the beg < end is the only thing stopping you from generalizing to a forward iterator.

---

As Ben Voigt noted, it would also be expected to generalize the comparator:

template<typename FwdIterator, typename Comparator>
void sort_selection(FwdIterator beg, FwdIterator end, Comparator cmp)

You would then either have the comparator default to std::less or you would have two functions: one that takes a comparator and one that just calls the comparator taking version with a std::less instance.

---

All in all, without going completely overboard, I would expect a sorting method to look something like this:

template<typename FwdIterator, typename Comparator>
void sort_selection(FwdIterator beg, FwdIterator end, Comparator cmp)
{
    for (; beg != end; ++beg)
    {
        FwdIterator min = std::min_element(beg, end, cmp); // auto if >= C++11
        if (cmp(*min, *beg))
            std::iter_swap(min, beg);
    }
}

template<typename FwdIterator>
void sort_selection(FwdIterator beg, FwdIterator end) {
    // using instead of typedef if >= C++11
    typedef typename std::iterator_traits<FwdIterator>::value_type value_type;
    sort_selection(beg, end, std::less<value_type>());
}

It might be worth noting that you don't actually need two methods. I just think it's a little cleaner than this:

template<typename FwdIterator, typename Comparator = std::less<typename std::iterator_traits<FwdIterator>::value_type>>
void sort_selection(FwdIterator beg, FwdIterator end, Comparator cmp = Comparator())