Insertion Sort Algorithm in C++.

The insertion Sort Algorithm is one of the simple (but not the best) sorting algorithms that is used to sort the array elements in ascending or descending order. In this article, we are going to understand the working and code implementation of this algorithm.

Insertion sort working is very similar to the way we sort playing cards in our hands. We assume that our first card is sorted and we will try to place our remaining unsorted cards in their correct position. In Insertion sort, an array is divided into sorted and unsorted parts and we have to take the elements from the unsorted part and place them in the sorted part of the array. This sorting algorithm is adaptive in nature and best for the data set which is partially sorted.

Working of Insertion Sort Algorithm.

Steps for Insertion Sort Algorithm.

Step 1: Run a loop to iterate all the elements of the array from 1 to n.

Step 2: Divide the given array into sorted and unsorted parts and assume that the first element is present in the sorted part of the array. 

Step 3: Pick the first element from the unsorted part of the array and compare it with elements present in the sorted part. 

Step 4: If you find all the elements present in the sorted part are smaller than the current element then include the current element into the sorted part and move to the next element, else find the correct position of the current element in the sorted part of the array and shift all the greater elements one unit right side to make space to insert the current element.

Step 5: Repeat the above steps until the entire array gets sorted. 

C++ Code Implementation for Insertion Sort Algorithm.

#include<iostream>
using namespace std;

//function for insertion sort
void insertionSort(int arr[], int n){
    int key, j;

    for(int i = 1; i < n; i++){
        key = arr[i];
        j = i-1;

        /*
        Moving the elements one position right
        that are greater than key to make space
        for key
        */
        while (j >= 0 && arr[j] > key)
        {
            arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j+1] = key;
    }
}
int main(){
    int arr[] = {7, 2, 4, 1, 5, 3};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);

    insertionSort(arr, n);

    //Printing the sorted Array
    cout<<"Sorted Array: ";
    for(int i = 0; i < n; i++){
        cout<<arr[i]<<" ";
    }
}

Output:

Sorted Array: 1 2 3 4 5 7

• Time Complexity: O(n^2)
• Space Complexity: O(1)