Template and insertion sort

I have written in the previous post a minimal C function that implements the insertion sort algorithm. It actually works, but it could be lot better. Here we are going to use some C++ functionality to make it stronger and more flexible.

We don't want many limits on the collection to be sorted, so we are passing to it two input iterators, one to the beginning the other to the end, and we want to use our function on almost any data type - we just require from it a support to comparison operator, so that we could actually sort the collection.

All these led to rewrite the function in this way:

template <typename InputIt, typename Compare> // 1.
void insertionSort(InputIt begin, InputIt end, Compare comp) // 2.
{
    if(end - begin < 2) // 3.
        return;

    for(InputIt cur = begin + 1; cur < end; ++cur) // 4.
    {
        std::iterator_traits<InputIt>::value_type temp = *cur; // 5.

        InputIt back = cur; // 6.
        for(;back > begin && comp(*(back-1), temp); --back) // 7.
            *(back) = *(back-1);
        *back = temp; // 8.
    }
}

1. It's a template function, based on the input iterator type and the comparison functor type we are about to use.
2. We pass to the function two iterators delimiting the interval on which we want to operate; the third parameter is the functor specifying how we want to sort the data. To get the usually expected behaviour (first element smaller, last element bigger) we should pass std::greater comparison functor.
3. This check was implicit in the C code of the previous example. Here we have to make it explicit: in case the passed collection has less than two elements, there is nothing to do.
4. External loop. We use another iterator, same type of the passed ones to the function, initialized to be the next after begin; and we loop until we reach the end.
5. The type declaration for the temp variable could look quite impressive. We want to have a local variable for storing the value referenced by cur; we don't actually have explicit access to this type, but it is implicitly available since we know the type of the iterators on it. The std::iterator_traits<InputIt> structure encapsulates the properties of the specified iterator, value_type is exactely what we were looking for. If the iterators passed to this function were defined to work on int, this value_type is set to int, so in this line we would actually say that temp was an int, and set to the value pointed by cur. We could have saved some typing using the C++0x auto type declaration:

auto temp = *cur;

Since the compiler could easily deduce the temp object type from the iterator dereferencing on the other side of the assignment operator.
6. We have to twist a bit the logic of the original C code here, since we are working on a stright iterator mimiking what should be the use of a reverse iterator. The problem is that there is nothing before the first valid iterator on a collection (while rend() would exactely referring to it) but the orginal code was designed to work in that way. Here we should work in a less natural way, initilizing our back iterator to be equals to the "end" iterator for the already ordered section of our collection, and using the element pointed by its predecessor.
7. Internal loop. We scan the left part of the collection, the "sorted" one, till we find elements that satisfy the comparator passed to the function, or we reach the collection left limit, moving each element one step to the right.
8. Finally, we put the temp value to its new (or back to its original) position.

It should be nice to the user programmer to provide an overload that requires just a couple of iterators, and uses the "normal" comparison operator:

template <typename InputIt>
void insertionSort(InputIt begin, InputIt end)
{
    typedef std::iterator_traits<InputIt>::value_type T;
    return insertionSort(begin, end, std::greater<T>());
}

Here is some unit tests I wrote during the development:

TEST(TestK02, Empty) {
    std::vector<int> vi;
    insertionSort(vi.begin(), vi.end());
    EXPECT_EQ(0, vi.size());
}

TEST(TestK02, Normal) {
    const int SIZE = 10;
    int values[SIZE] = { 42, 12, 94, 45, 1, 55, 95, 34, 73, 29 };
    std::vector<int> vi(values, values + SIZE);

    insertionSort(vi.begin(), vi.end());

    // vector expected sorted
    for(int i = 1; i < SIZE; ++i)
        EXPECT_GE(vi[i], vi[i-1]);
}

TEST(TestK02, Strings) {
    const int SIZE = 10;
    std::string values[SIZE] = { "ft", "te", "nf", "ab", "o", "fr", "ng", "tf", "st", "tn" };
    std::vector<std::string> vi(values, values + SIZE);

    insertionSort(vi.begin(), vi.end());

    // vector expected sorted increasing
    for(size_t i = 1; i < vi.size(); ++i)
        EXPECT_GE(vi[i], vi[i-1]);
}

TEST(TestK02, StrDecr) {
    const int SIZE = 10;
    std::string values[SIZE] = { "ft", "te", "nf", "ab", "o", "fr", "ng", "tf", "st", "tn" };
    std::vector<std::string> vi(values, values + SIZE);

    insertionSort(vi.begin(), vi.end(), std::less<std::string>());

    // vector expected sorted decreasing
    for(size_t i = 1; i < vi.size(); ++i)
        EXPECT_LE(vi[i], vi[i-1]);
}