How to implement insertion sort in C++ and C

Sorting is a method organizes given information in a particular order. We must sort the data we use in a given order to make it easier to retrieve an appropriate bit of data from the data pile. If the data is messy and not sorted, or if we want a specific bit of information, we will need to check each element one by one every time for it to get the data.

Insertion sort is a simple sorting algorithm that tests one object at a time to get the final sorted array.

It is much less efficient on large arrays than more sophisticated algorithms like merge sort, heapsort, or quicksort.

The array is first divided into sorted and unsorted portions – the values of the unsorted portion are moved to the correct place in the sorted portion. Essentially, insertion sort sorts an array of elements in order by comparing each element with the previous elements and transferring elements accordingly.

Algorithm

Iterate over the input elements by increasing the sorted array at each iteration.
Compare the current element with the largest available value in the sorted array.
If the current element is larger than the largest value in the array, it will leave the element in its place and move to the next element.
Otherwise, it will find its correct location in the sorted array and move it to that position in the array. This is done by moving all the elements that are larger than the current element into the sorted array to the next position.

Visualization

Now, let’s see a visualization of the insertion sort algorithm.

//C++ program for implementation of Insertion Sort 
#include<iostream>
using namespace std; 
//A function to sort the array using insertion sort
void inSort(int a[], int n)
{  
    int i,j, k;  
    for (i = 1; i < n; i++) 
    {  
        k = a[i];  
        j = i - 1;  
        /*Move elements of arr[0..i-1], that are  
        greater than k, to one position ahead  
        of their current position */
        while (j >= 0 && a[j] > k) 
        {  
            a[j + 1] = a[j];  
            j = j - 1;  
        }  
        a[j + 1] = k;  
    }  
}  
// A function to print an array of size n  
void print(int a[], int n)  
{  
    int i;  
    for (i = 0; i < n; i++)  
        cout << a[i] << " ";  
    cout << endl; 
}  
  
//Driver code for testing above code
int main()  
{  
    int a[] = { 5,2,8,7,3,5,4,1 };  
    int n = sizeof(a) / sizeof(a[0]);  
    inSort(a, n);  
    print(a, n);  
    return 0;  
}

Time and space complexity

Insertion sort is a sorting algorithm that creates a sorted array one element at a time. Although sorting is a simple concept, it is a fundamental principle used in complex tasks such as file search, data compression, and pathfinding.

Running time plays an important role when selecting a sorting algorithm, as performance is often thought of in terms of speed. Insertion sort has an average and worst-case running time. In most situations, a faster algorithm is much more preferable.

Best-case time complexity - [ O(n) ]
Average-case time complexity - [ O(n²) ]
Worst-case time complexity - [ O(n²) ]
Space complexity - [ O(n²) ]

Important characteristics of insertion sort

• Effective for smaller data sets, but rather inefficient for larger lists.

• Insertion Sort is adaptive, which means that it decreases its total number of steps if the array is partially sorted, thus enhancing its performance.

• The space complexity is less. Insertion sort only needs a single additional memory space.

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

How to implement insertion sort in C++ and C

Algorithm

Visualization

Implementation

Time and space complexity

Important characteristics of insertion sort