# 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.

# Implementation

Here is the `insertion_sort`

and `insertion_sort_stl`

function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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.

1
2
3
4
5
6
7
8
9
10
11

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.

### C++ implementation of Insertion Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#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);
}

View this code on Github

Get this post in pdf - Insertion Sort

Reference:

Introduction to Algorithms

The Algorithm Design Manual

Data Structures and Algorithms Made Easy

Competitive Programmer’s Handbook - Antti Laaksonen

### You may also like