C++ Program For Insertion Sort

Insertion sort works similarly as we sort cards in our hand in a card game.

We assume that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In the same way, other unsorted cards are taken and put at their right place.

A similar approach is used by insertion sort.

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration. 

Program:

#include <iostream>
using namespace std;

void insertionSort (int arr[], int n)	//function of insertion sorting
{
  for (int i = 1; i < n; i++)
    {
      int temp = arr[i];
      int j = i - 1;
      
      while (j >= 0 && arr[j] > temp)
	    {
	        arr[j + 1] = arr[j];
	        j--;
	    }
	    
      arr[j + 1] = temp;
    }
}

int main ()
{
  int arr[] = { 7, -5, 2, 16, 4 };

  int n = sizeof (arr) / sizeof (arr[0]);	//getting size of array

  insertionSort (arr, n);	//funtion call

  cout << "Sorted array:" << endl;
  
  for (int i = 0; i < n; i++)	//printing sorted array
    cout << arr[i] << " ";
    
  return 0;
}

Output:

Sorted array:
-5 2 4 7 16