Sorting algorithms - Insertion sort

Question

^{This is a follow-up question to Sorting algorithms - Bubble sort}

Again, for practice purposes only, I took on an implementation of the well known insertion sort as a method to be used similarly to std::sort.

As expected, the code lives inside a header file called insertion_sort.h:

#pragma once

#include <iterator>
#include <algorithm>

namespace sorting_algorithms {
    template <typename BidirectionalIterator,
            typename Comparator = std::less<>>
    void insertion_sort(BidirectionalIterator begin, BidirectionalIterator end,
            Comparator cmp = {}) {

        if (std::distance(begin, end) < 2) {
            return;
        }

        for (auto current_element = std::next(begin); current_element != end;
                ++current_element) {
            for (auto i = std::prev(current_element), i_next = current_element;
                    i_next != begin; --i, --i_next) {
                auto& i_val = *i;
                auto& i_next_val = *i_next;
                if (cmp(i_val, i_next_val)) {
                    break;
                }
                std::iter_swap(&i_val, &i_next_val);
            }
        }
    }
}

I tried to follow most hints and suggestions I received for my previous question about bubble sort. I am aware of the fact that the algorithm can also be implemented in a way that only requires forward iterators, but I decided to require bidirectional iterators here for ease of implementation.

Again, I also provide you a main file for simple compilation and testing purposes:

#include <random>
#include <vector>
#include <iostream>
#include <iomanip>
#include <chrono>
#include <algorithm>

#include "insertion_sort.h"

int main() {
    unsigned seed =
        std::chrono::system_clock::now().time_since_epoch().count();
    std::default_random_engine engine(seed);
    std::uniform_int_distribution<unsigned> distribution(0, 10000);

    std::vector<unsigned> vec;
    for (std::size_t i = 0; i < 100; ++i) {
        unsigned num = distribution(engine) + 1;
        std::cout << num  << ' ';
        vec.push_back(num);
    }
    std::cout << "\n\n";

    sorting_algorithms::insertion_sort(vec.begin(), vec.end());

    for (const auto& e : vec) {
        std::cout << e << ' ';
    }

    std::cout << std::boolalpha;
    std::cout << "\nSorted? " << std::is_sorted(vec.begin(), vec.end())
        << "\n\n";

    sorting_algorithms::insertion_sort(vec.begin(), vec.end(),
            [] (const auto& v0, const auto& v1) {
                return v0 > v1;
            });

    for (unsigned e : vec) {
        std::cout << e << ' ';
    }
    std::cout << "\nSorted (in reverse order)? "
        << std::is_sorted(vec.begin(), vec.end(),
            [] (const auto& v0, const auto& v1) {
                return v0 > v1;
            }) << '\n';
}

Answer 1

Important stuff:

• Missing header:

The std::less<> is from <functional>.

• Relying on type deduction:

Although it is generally good, the lines

            auto& i_val = *i;
            auto& i_next_val = *i_next;

seem somewhat dangerous to me. For std::vector<bool>, for example. I think it should be at least const auto&, or even better, the comparison could be called without them:

cmp(*i, *i_next);

• Dangerous swap:

          auto& i_val = *i;
          auto& i_next_val = *i_next;
          if (cmp(i_val, i_next_val)) {
              break;
          }
          std::iter_swap(&i_val, &i_next_val);
  

The swap assumes that types didn't overload operator&. It is pretty rare these days, but still exist. The swap should just be std::iter_swap(i, i_next).

Style:

• Complicated inner loop:

The control flow inside of the loop is very hard to follow. This is the version in my library:

        auto j = i;
        while (std::prev(j) != first && !cmp(*std::prev(j), *j))
        {
            std::iter_swap(std::prev(j), j);
            --j;
        }

The i is the iterator of the outer loop. It might not be that descriptive, but I think it is ok. The main idea here is that while loop is used and the condition is inside of the condition brackets, which closely follows plain english description of an algorithm.

• Naming:

Usually range is denoted by [first, last). At least this is what I see quite frequently on cppreference. Also, the concept is called Compare, so it might be worth sticking to it, although it is somewhat confusing.

Testing:

There is std::greater template function object which could be used instead of handwritten lambda.

Answer 2

    if (std::distance(begin, end) < 2) {
        return;
    }

While distance is constant complexity for random access iterators, it is calculated in linear time for bidirectional iterators. Rather than checking the full range, check the non-existence of the first value.

    if (begin == end || std::next(begin) == end) {
        return;
    }

---

    for (auto i = std::prev(current_element), i_next = current_element;
             i_next != begin; --i, --i_next) {
         auto& i_val = *i;
         auto& i_next_val = *i_next;
         if (cmp(i_val, i_next_val)) {
             break;
         }

For bidirectional iterators, decrementing beyond the first element is undefined behavior. While it has no negative effect in this context, it's something you should be aware of.

Don't be afraid to break functions up into smaller functions of its logical parts and parameterize them. What you've written is a reverse linear search while swapping an element until it is in its sorted position. The c++ standard library provides a predicated linear search (std::find_if_not) that can be utilized in reverse (std::reverse_iterator<>) and can slide an element into a position (std::rotate). See "How to implement classic sorting algorithms in modern C++?". Be sure to check the examples to see how you can reduce the boilerplate in your test cases.

---

#include <random>
#include <vector>
#include <iostream>
#include <iomanip>
#include <chrono>
#include <algorithm>

#include "insertion_sort.h"

From John Lakos in Large-Scale C++ Software Design (Addison-Wesley, 1996):

Latent usage errors can be avoided by ensuring that the .h file of a component parses by itself – without externally-provided declarations or definitions... Including the .h file as the very first line of the .c file ensures that no critical piece of information intrinsic to the physical interface of the component is missing from the .h file (or, if there is, that you will find out about it as soon as you try to compile the .c file).

To summarize, use the following ordering:

1. The prototype/interface header for this implementation (ie, the .h/.hh file that corresponds to this .cpp/.cc file).
2. Other headers from the same project, as needed.
3. Headers from other non-standard, non-system libraries (eg, Folly, Qt, etc).
4. Headers from other "almost-standard" libraries (eg, Boost)
5. Standard C++ headers (eg, algorithm, iostream, etc)
6. Standard C headers (eg, windows.h, dirent.h, etc)

Your main test file would look like (lexicographically sorted for faster mental searches):

#include "insertion_sort.h"

#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>

For insertion_sort.h, don't rely on other headers providing your missing headers.

#include <algorithm>  // std::iter_swap
#include <functional> // std::less<>
#include <iterator>   // std::distance, std::prev

---