Insertion Sort Program in C++

Today we will learn the Insertion Sort Program in C++. So before starting you should have a little bit knowledge about insertion sorting.

Table of Contents

What is Insertion Sort?

The basic idea of this method is to place an unsorted element into its correct position in a growing sorted list of elements. We select one element from the unsorted set at a time and insert it into its correct position in the sorted set.

The Process continues till the unsorted set becomes empty.

For Example:

In order to arrange playing cards, we pick one card at a time and insert this card in its proper position in the cards held in the hand.

Illustration:

Given Data is: 15 7 22 3 14 2

when a new element is to be inserted into the sorted list, it is compared with the elements in the sorted list and inserted at its correct place.

This is done by shifting elements which are greater than the element one position to the right. The comparison is done backwards from the last element.

For example, to insert 14 in the example above, it is first compared with 22. Since 22>14, 22 is shifted right. Then it is compared with 15. Since 15>14, 15 is shifted right. Then it is compared with 7, Since 7<14, 14 is placed to the right of 7.

The Insertion Process begins from the second element since the first element can be directly placed in the sorted set at position 0.

Insertion Sort Algorithm:

Let x is an array of n elements. x[0] may be considered as a sorted array of one element. The unsorted list is x[1] to x[n-1].

1st Step: START.

2nd Step: j=1 i.e unsorted position starts from 1.

3rd Step: key=x[j].

4th Step: i=j-1 i.e sorted set starts from j-1.

5th Step: while x[i]>key and i>=0 then x[i+1]=x[i]. i.e shift element to the right.

6th Step: x[i+1]=key i.e insert key in correct position.

7th Step: j=j+1 i.e next unsorted element.

8th Step: If j<n go to step 3.

9th Step: STOP.

Efficiency of Insertion Sort:

Best Case: If the initial data is sorted, only one comparison is made in each pass i.e each element will be compared only with the last element in the sorted list. So the best case time complexity is O(n).

Example: If the elements are 2,3,7,14,15,22 then 3 is compared only with 2, 7 with 3, 14 with 7 and so on.

Worst case: If the initial data is in the reverse order each element will be compared with each element in the sorted list.

Example: If the elements are 22,15,14,7,3,2 then 15 is compared with 22, 14 is compared with 22 and 15,7 is compared with 22,15 and 14, 3 is compared with 22,15,14 and 7 and so on.

The total number of comparisons for the n-1 passes will be 1+2+…+(n-1) = n(n-1) / 2 which is O(n^2).

Advantages:

It is a simple sorting method.

It is in-place sorting method.

It’s a Stable sorting method.

Best case complexity is O(n).

Most suitable sorting method if the elements are almost sorted.

Disadvantages:

Worst Case efficiency is O(n^2).

<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>//Learnprogramo - programming made simple
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n)
{
  int k, key, ptr;
  for (k = 1; k < n; k++)
  {
    key = arr[k];
    ptr = k - 1;
    while (ptr >= 0 && arr[ptr] > key)
    {
      arr[ptr + 1] = arr[ptr];
      ptr = ptr - 1;
    }
    arr[ptr + 1] = key;
  }
}
int main()
{
  int n;
  cout << "Enter Size of the Array: ";
  cin >> n;
  int arr[n], i;
  cout << "Enter values of the array\n";
  for (i = 0; i < n; i++)
    cin >> arr[i];
  insertionSort(arr, n);
  cout << "Array after Insertion Sort is: ";
  for (i = 0; i < n; i++)
    cout << arr[i] << " ";
  return 0;
}</pre>
</div>

Output:

In the above program, the compiler asks the user to enter the n elements and stored in the array arr. Then we are comparing those elements so they can be arranged properly using insertion sort. And then print on the screen.

Run time Test Cases:

1st Case: Average Case-

In this case, elements are entered in random order.