How to Implement the Insertion Sort Algorithm in C++

This article will demonstrate how to implement an insertion sort algorithm in C++.

Implement the Insertion Sort for the std::vector Container in C++

In this guide, we will show you how to implement the insertion sort as a separate function that takes a reference to the std::vector object and modifies the contents in place. The insertion sort iterates through each element in the vector. It makes sure that all elements before the current position are sorted by comparing the current element with the previous ones in backward order.

Generally, the order of comparison does not matter much in the algorithm performance, but we assume the backward order and implement the code correspondingly. We’ll also assume to be sorting the elements in ascending order. Still, in actual cases, the generic sorting algorithm should be able to take a custom comparison function as an argument. Notice that the comparison operation often forces the element to be shifted right if the current element is lesser than the previous one. The latter operation is implemented using another nested for loop, which invokes the std::swap function on elements that are in the wrong order.

The following code snippet includes the insertionSort function where the outer for loop is responsible for the whole array traversal. We initialize the iterator to the second element in the vector because the next steps include the comparison to the previous ones - the inner loop iterates from the current element down to the first one to compare them. If the comparison function evaluates true, the pair is swapped. Note that the else expression forces the inner loop to break when at least one previous element turns out to be less than the current element.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void insertionSort(vector<T> &vec) {
  for (auto it = vec.begin() + 1; it != vec.end(); ++it) {
    auto key = it;

    for (auto i = it - 1; i >= vec.begin(); --i) {
      if (*i > *key) {
        std::swap(*i, *key);
        key--;
      } else {
        break;
      }
    }
  }
}

int main() {
  vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};

  printVector(vec1);
  insertionSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Output:

43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;

Alternatively, we can reimplement the insertionSort function using while loop constructs if the latter is preferred as a more readable form for the user. Two algorithms follow a similar implementation logic, and both utilize the std::swap function to shift elements. The insertion sort is quite an inefficient algorithm on large data sets, and its average performance is O(n²).

Insertion sort is similar to another quadratic algorithm called the selection sort; they both iterate through the vector. After the n iterations, the first n elements are sorted. Although, the selection sort evaluates forward elements from the current position in contrast to the insertion sort.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void insertionSort2(vector<T> &vec) {
  auto iter = vec.begin() + 1;
  while (iter != vec.end()) {
    auto key = iter;
    auto it = iter - 1;

    while (it >= vec.begin() && *it > *key) {
      std::swap(*it, *key);
      key--;
      it--;
    }
    iter++;
  }
}

int main() {
  vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};

  printVector(vec1);
  insertionSort2(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Output:

43; 5; 123; 94; 359; -23; 2; -1; 
-23; -1; 2; 5; 43; 94; 123; 359; 

The insertion sort can be more efficient in practice compared to other O(n²) algorithms because it does not always need to compare the current element with every preceding one. Meanwhile, the selection sort must always search through every element in the unsorted subarray to find the smallest(or the largest) element. Notice that we can utilize both the insertionSort function implementation on the vector of std::string as the latter class implements the comparison operator overloads. The next example demonstrates its basic usage with the string vector and prints the sorted list of words.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void insertionSort(vector<T> &vec) {
  auto iter = vec.begin() + 1;
  while (iter != vec.end()) {
    auto key = iter;
    auto it = iter - 1;

    while (it >= vec.begin() && *it > *key) {
      std::swap(*it, *key);
      key--;
      it--;
    }
    iter++;
  }
}

int main() {
  vector<string> vec2 = {"highway", "song",  "work",
                         "borland", "death", "woman"};

  printVector(vec2);
  insertionSort(vec2);
  printVector(vec2);

  return EXIT_SUCCESS;
}

Output:

highway; song; work; borland; death; woman;
borland; death; highway; song; woman; work;