2
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Could be min_element(beg+1, end) right? \$\endgroup\$ – Ben Voigt Apr 26 '15 at 20:35
  • 2
    \$\begingroup\$ And what about support for a comparator other than operator<? \$\endgroup\$ – Ben Voigt Apr 26 '15 at 20:36
  • \$\begingroup\$ Thanks for the comments @BenVoigt. Corbin included them in his more in-depth review. \$\endgroup\$ – Francisco Aguilera Apr 26 '15 at 21:56
6
\$\begingroup\$

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())
\$\endgroup\$
  • 1
    \$\begingroup\$ @Edward When it's just a snippet and not an entire program, I tend to assume the poster has required the proper headers. \$\endgroup\$ – Corbin Apr 26 '15 at 21:40
  • 1
    \$\begingroup\$ @FranciscoAguilera Glad it was helpful :). Since you don't want the caller's iterators to be mutated, you need to take them by either value or const reference. Since beg is modified, value makes more sense. In the case of end, since it's not modified, it could have been taken by const reference. However, iterators are usually very cheap to copy (after all, they're usually glorified pointers), so I just took a copy. \$\endgroup\$ – Corbin Apr 26 '15 at 22:00
  • 1
    \$\begingroup\$ It's a surprisingly complicated issue when it comes down to it: What if const methods aren't defined? What if const-ref is actually less efficient than a copy? So on. I tend to always favor value over const-ref for iterators unless I know that an expensive to copy iterator is going to be used with the function (and now that I think about it, I can't actually even remember the last time that happened). \$\endgroup\$ – Corbin Apr 26 '15 at 22:01
  • 1
    \$\begingroup\$ @FranciscoAguilera That is also a surprisingly complicated question to answer. The short answer is that as long as you use C++ functionality wisely and are mindful of what's going on, it can be as efficient or even more efficient than C with regards to time/memory usage. std::vector is a good example of something that breaks even: as long as you're mindful of use (for example, reserving space up front instead of allowing it to grow if you know the size), once the compiler does its optimizing magic, it is essentially the same a bare malloc()'d array. \$\endgroup\$ – Corbin Apr 26 '15 at 22:54
  • 1
    \$\begingroup\$ @FranciscoAguilera std::sort vs qsort is the canonical example of a C++ thing that is more efficient than a C version. It turns out the aggressive inlining that templates can allow means that std::sort not only gets to be typesafe and far easier to use, but it also doesn't have to dereference a pointer and call a function with each comparison. Depending on different benchmarks/setups, some people report absurdly better numbers for std::sort, and I've never seen a benchmark where qsort is faster. \$\endgroup\$ – Corbin Apr 26 '15 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.