Wednesday, December 5, 2018
Home > C++ > Insertion Sort C++

# Insertion Sort C++

Insertion sort is an algorithm for sorting a list of items (array). It sorts the given list of items in either ascending or descending order depending upon its implementation. Insertion sort algorithm works exactly the same way as we place cards in our hand. i.e. placing each card at its right position. Talking about the efficiency of insert sort algorithm, it is not the much faster algorithm for sorting yet it provides some benefits as well.

• It is much simpler to implement in any programming language.
• Faster for smaller data set.
• Can sort any list that it receives.

## Algorithm

The algorithm for insertion sort is very simple. For a given list of elements:

In each iteration, it takes an input element and places it in its proper position. Thus forming a sorted list of output elements. This process is repeated until no element in the input list remains placed in its position.

For each input item in the array, it checks for the largest value in the sorted array. If the input value is larger than the largest value in the sorted array it leaves the input value at its current position and moves to the next iteration. Otherwise, if the input value is smaller it finds the correct position for it and shifts all the larger values to the next positions to make a place for the input value at the correct position.

Let’s have a look at the below example

Below is an unsorted integer array.

 10 5 11 9 1

The algorithm takes 5 the 2nd value and compares it with 10. As it is less than 10 so it moves 10 to the next position and places 5 at the start.

 5 10 11 9 1

Now in the 2nd iteration, it takes 11 from the input array and compares it with 10. As 11 is larger than 10 so it will not move the elements of the array.

 5 10 11 9 1

In the 3rd iteration, the input element 9 is picked from the array and compared with 11. 9 is less than 11 so it will again compare it with the 2nd largest value as well. 9 is also lesser than 10. So, it compares it with the 3rd largest value which is 5. As 9 is larger than 5 so the correct position for 9 is after 5 and before 10. So our array will look like

 5 9 10 11 1

In the next iteration, it takes the next input element. Which in our case is 1. The algorithm will compare it with the values and results in finding its correct position. Thus the array will be:

 1 5 9 10 11

As the last element is also placed in its proper position so our input array is now sorted.

## Pseudocode for insertion sort

Let us have an array named as myArray

```i ← 1

while i < length(myArray)

j ← i

while j > 0 and myArray[j-1] > myArray[j]

swap myArray[j] and myArray[j-1]

j ← j - 1

end while

i ← i + 1

end while```

As we can see that in the pseudocode the iteration starts from the 2nd element of the array. This is because for the first element we don’t have any value with which we can compare it or replace it.

## Insertion Sort C++ code

Let’s have a look at the implementation of Insertion sort in C++.  Below two programs show us how we can sort an array using insertion sort in C++. The first program sorts the array in the ascending order while the 2nd program sorts the same array in the descending order.

### Insertion sort C++ code for sorting array in ascending order.

```#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <math.h>

using namespace std;
void sort_insertion(int myArr[], int size)
{
int input;
for (int i = 1;i<size;i++)
{
input = myArr[i];
int j = i - 1;
while ( j >= 0 && myArr[j] > input )
{
myArr[j + 1] = myArr[j];
j--;
}
myArr[j + 1] = input;
}
}
void display(int myArr[], int size) {
for (int i = 0;i<size;i++)
{
cout << myArr[i] << " ";
}
}
int main() {
int *arr;
int size;
cout << "Please enter the size of array: ";
cin >> size;
arr = new int[size];
cout << "Please Enter Values for array \n";
for (int i = 0; i < size;i++) {
cout << "Value at index "<<i+1<<" : ";
cin >> arr[i];
}
sort_insertion(arr, size);
cout << "\n\nSorted Array is\n";
display(arr, size);
return 0;
}```

### Insertion sort C++ code for sorting array in descending order.

Note: – if you want to just display the sorted array in descending order. Then you don’t need to sort in descending order. You just sort it in ascending order and display it in reverse order.

```#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <math.h>

using namespace std;
void sort_insertion(int myArr[], int size)
{
int input;
for (int i = 1;i<size;i++)
{
input = myArr[i];
int j = i - 1;
while (j >= 0 && myArr[j] > input)
{
myArr[j + 1] = myArr[j];
j--;
}
myArr[j + 1] = input;
}
}
void display(int myArr[], int size) {
for (int i = size-1;i>=0;i--)
{
cout << myArr[i] << " ";
}
}
int main() {
int *arr;
int size;
cout << "Please enter the size of array: ";
cin >> size;
arr = new int[size];
cout << "Please Enter Values for array \n";
for (int i = 0; i < size;i++) {
cout << "Value at index "<<i+1<<" : ";
cin >> arr[i];
}
sort_insertion(arr, size);
cout << "\n\nSorted Array is\n";
display(arr, size);
return 0;
}```

In this above example, we just sort the array in the ascending order and then while displaying it. We just reversed the order. But It is not the only way we can sort the array in descending order. Have a look at this below program.

```#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <math.h>

using namespace std;
void sort_insertion(int myArr[], int size)
{
int input;
for (int i = 1;i<size;i++)
{
input = myArr[i];
int j = i-1;
while (j >=0 && myArr[j] < input)
{
myArr[j+1] = myArr[j];
j--;

}
myArr[j+1] = input;
}
}
void display(int myArr[], int size) {
for (int i = 0;i<size;i++)
{
cout << myArr[i] << " ";
}
}
int main() {
int *arr;
int size;
cout << "Please enter the size of array: ";
cin >> size;
arr = new int[size];
cout << "Please Enter Values for array \n";
for (int i = 0; i < size;i++) {
cout << "Value at index "<<i+1<<" : ";
cin >> arr[i];
}
sort_insertion(arr, size);
cout << "\n\nSorted Array in Descending order is\n";
display(arr, size);
return 0;
}```

## Recursive insertion sort in c++

Recursive insertion sort is not a new algorithm for sorting yet it is the recursive implementation of insertion sort algorithm. The recursive implementation does not have any impact on the efficiency or performance of the algorithm. Though it helps in measuring one’s understanding of recursion and insertion sort algorithm.

In terms or recursion, we can divide the Insertion sort algorithm as

• Base Case: If the size of the array is 1 or smaller, then return (do not proceed further for sorting).
• Sort the first n-1 elements recursively.
• Insert the last input element at its correct position in the sorted array.

### Pseudocode

```INSERTION_SORT(Arr,size)
if size > 1
then INSERTION_SORT(Arr,size-1)
input = A[size]
j = size-1
while j > 0 and A[j] > input
A[j+1] = A[j]
j = j - 1
A[ij+ 1] = input```

### Ascending

```#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <math.h>

using namespace std;
void sort_insertion(int myArr[], int size)
{
if (size <= 1) {
return;
}
else {
sort_insertion(myArr, size - 1);
int input = myArr[size - 1];
int j = size - 2;
while (j >= 0 && myArr[j] > input)
{
myArr[j + 1] = myArr[j];
j--;
}
myArr[j + 1] = input;      }
}
void display(int myArr[], int size) {
for (int i = 0;i<size;i++)
{
cout << myArr[i] << " ";
}
}
int main() {
int *arr;
int size;
cout << "Please enter the size of array: ";
cin >> size;
arr = new int[size];
cout << "Please Enter Values for array \n";
for (int i = 0; i < size;i++) {
cout << "Value at index "<<i+1<<" : ";
cin >> arr[i];
}
sort_insertion(arr, size);
cout << "\nUsing recursive insertion";
cout << "\n\nSorted Array in Descending order is\n";
display(arr, size);
return 0;
}```

### Descending

```#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <math.h>

using namespace std;
void sort_insertion(int myArr[], int size)
{
if (size <= 1) {
return;
}
else {
sort_insertion(myArr, size - 1);
int input = myArr[size - 1];
int j = size - 2;
while (j >= 0 && myArr[j] < input)
{
myArr[j + 1] = myArr[j];
j--;
}
myArr[j + 1] = input;      }
}
void display(int myArr[], int size) {
for (int i = 0;i<size;i++)
{
cout << myArr[i] << " ";
}
}
int main() {
int *arr;
int size;
cout << "Please enter the size of array: ";
cin >> size;
arr = new int[size];
cout << "Please Enter Values for array \n";
for (int i = 0; i < size;i++) {
cout << "Value at index "<<i+1<<" : ";
cin >> arr[i];
}
sort_insertion(arr, size);
cout << "\nUsing recursive insertion";
cout << "\n\nSorted Array in Descending order is\n";
display(arr, size);
return 0;
}

```

This site uses Akismet to reduce spam. Learn how your comment data is processed.