C++ Program To Insertion Sort Using Dynamic Array

In this tutorial, we are going to learn the algorithm of insertion sort.

Insertion sort works by dividing the array or list into two parts i.e. one is a sorted sublist and another one is an unsorted sublist. The logic is to pick one element from the unsorted subarray and place it at the appropriate position in the sorted subarray. Similarly, we will keep on exchanging the position in the sorted and unsorted subarrays till there is no element in the unsorted subarray.

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration. Insertion sort works similarly as we sort cards in our hands 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 in their right place.

Let us consider some inputs to understand what should be the required output:

Input:

array: {2 3 9 7 1}

Output:

array: {1 2 3 7 9}

Input:

array: {56 9 11 7 60}

Output:

array: {7 9 11 56 60}

Insertion Sort Algorithm

Step1: The first element in the array is assumed to be sorted. Take the second element and store it separately in "k". Compare "k" with the first element. If the first element is greater than "k", then "k" is placed in front of the first element.

Step2: Now, the first two elements are sorted. Take the third element and compare it with the elements on its left. Placed it just behind the element smaller than it. If there is no element smaller than it, then place it at the beginning of the array.

Step3: Similarly, place every unsorted element at its correct position.

Step4: The above process goes on until the last element.

C++ Program for Insertion Sort

#include<iostream>
using namespace std;

int insertion_sort(int n,int array[]){
    int j;
    for(int i=1;i<n;i++){
        int temp=array[i];
        j=i-1;
        while(j>=0 && array[j]>temp){
            array[j+1]=array[j];
            j--;
        }
        array[j+1]=temp;
    }
    return 0;
}

int main(){
    int arr[]={5,9,3,2,4,10,6};
    int n=sizeof(arr)/sizeof(arr[0]);
    insertion_sort(n,arr);
    cout<<"Elements after sorting the array are:- ";<<endl;
    for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}

Elements after sorting the array are:-
2 3 4 5 6 9 10

Conclusion

We have seen the logic or the basic idea behind the working of insertion sort. Also with the help of an example, we have implemented the algorithm of insertion sort.