Insertion Sort | C++ Implementation

Insertion sort is an efficient algorithm for sorting a small number of elements. The algorithm selects an element from the unsorted array and put it in the proper position in the sorted. This process is repeated until all elements in the array are sorted. The sorting is in-place means array consists of sorted portion and unsorted portion in it.

The index of the key starts from 1. The algorithm finds the correct position of the key in the array and put the key at that position and then the element with next index becomes key.

In fig. (d) the index of key is 4 and value is 1. Since 1 is the smallest element in the array so far, so it is shifted to index 0.

Here is the insertion_sort and insertion_sort_stl function.

void insertion_sort(std::vector<int>& vec)
{
    for(std::size_t j = 1; j < vec.size(); j++)
    {
      int key = vec[j];
      int i = j-1;

      while(i >= 0 && vec[i] > key)
      {
         vec[i+1] = vec[i];
         i--;
      }
      vec[i+1] = key;
    }
}

We can also use functions from C++ Standard Template Library for insertion sort.

void insertion_sort_stl(std::vector<int>& vec)
{
	for(auto it = vec.begin(); it != vec.end(); it++)
 	{
   		// Search
   		auto const insertion_point = std::upper_bound(vec.begin(), it, *it);

   		//insert
   		std::rotate(insertion_point, it, it+1);
 	} 
}

upper_bound returns an iterator pointing to the first element in the range [first, last) whose value is larger than the x. Here x is *it.

rotate perfoms left rotation. It swaps the elements in the range [first,last), in such a way that the element pointed by middle becomes the new first element and element pointed by middle-1 becomes last element.

For eg. Given array is { 5, 2, 4, 6, 1, 3} and iterator middle points to 4. After rotation array becomes {4, 6, 1, 3, 5, 2} which is left rotation 2 times.

Here the middle element is *it and pointed by iterator it.

So when array is { 2, 5, 4, 6, 1, 3 } and in the range [2, 4), 5 is the greatest so insertion_point points to 5 and it points to 4. rotate is applied for the range [5, 6) and it is the middle element so 4 becomes the first element in the range and array becomes { 2, 4, 5, 6, 1, 3 }

Here is the position of elements in the array after each iteration.

#include <iostream>
#include <vector>

void insertion_sort(std::vector<int>& vec)
{
    for(std::size_t j = 1; j < vec.size(); j++)
    {
      int key = vec[j];
      int i = j-1;

      while(i >= 0 && vec[i] > key)
      {
         vec[i+1] = vec[i];
         i--;
      }
      vec[i+1] = key;
    }
}

void print(std::vector<int>& vec) 
{
    for(unsigned i = 0; i < vec.size(); i++)
    {
        std::cout << vec[i] << " ";
    }
    std::cout << "\n";
}

int main()
{
    std::vector<int> arr = {5, 2, 4, 6, 1, 3};
    insertion_sort(arr);
    print(arr);
}

Reference: Introduction to Algorithms The Algorithm Design Manual Data Structures and Algorithms Made Easy Competitive Programmer’s Handbook - Antti Laaksonen