Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

Insertion sort is a sorting algorithm in which the elements are transferred one at a time to the right position.

In other words, an insertion sort helps in building the final sorted list, one item at a time, with the movement of higher-ranked elements. It has the benefits of simplicity and low overhead.

The array is searched sequentially, and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its average and worst-case complexity is of Ο(n^2 ), where n is the number of items.

What is the Insertion Sort Algorithm?

Insertion sort is an easy comparison-based Sorting algorithm. The insertion sort algorithm starts to compare the first two elements in the array. If the first element is bigger than the second element, they are exchanged with each other. This process is implemented for all neighbor-indexed elements.

Here's an algorithm for Insertion Sort:

insertionSort(array)
mark the first element as sorted
for each unsorted element Xs
‘extract’ the element X
for j <- lastSortedIndex down to 0 if current element j > X
move sorted element to the right by 1
break loop and insert X here
end insertionSort

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Working of Insertion Sort

Let’s take an example: Take an array A[] = [ 7, 5, 4, 2 ]

Since 7 is the first element that has no other element to be compared with, it remains at its position. Now when on moving towards 4, 7 is the largest element in the sorted list and greater than 4. So, move 4 to its correct position, i.e., before 7. Similarly, with 5, as 7 (the largest element in the sorted list) is greater than 5, we will move 5 to its correct position. Finally, for 2, all the elements on the left side of 2 (sorted list) are moved one position forward as all are greater than 2, and then two is placed in the first position. Finally, the given array will result in a sorted array.

Implementation of Insertion Sort

Insertion Sorting in C

Following C program asks the user to enter the array size and array element to sort the array using the insertion sort technique, then display the sorted array on the screen:

// C program for insertion sort

/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i – 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j – 1;
}
arr[j + 1] = key;
}
}
// print an array of size n
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
printf(“%d “, arr[i]);
printf(“\n”);
}
/* program to test insertion sort */
int main()
{
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n); printArray(arr, n); return 0;
}

Insertion Sorting in C++

Following C++ program asks the user to enter the array size and array element to sort the array using the insertion sort technique, then display the sorted array on the screen:

/* C++ Program – Insertion Sort */

C++

C++

#include <iostream> using namespace std; int main() { int size, arr[50], i, j, temp; cout<<"Enter Array Size : "; cin>>size; cout<<"Enter Array Elements : "; for(i=0; i < size;i++){ cin>>arr[i]; } cout<<"Sorting array using selection sort … \n"; for (i = 1; i < size; i++) { temp = arr[i]; j = i - 1; while (j >= 0 && arr[j] > temp) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = temp; }

Following Java Program asks the user to enter the array size and array element to sort the array using the insertion sort technique, then display the sorted array on the screen:

/* Java Program Example – Insertion Sort */

import java.util.Scanner;
public class Main
{
public static void main(String args[])
{
int size, i, j, temp;
int arr[] = new int[50];
Scanner scan = new Scanner(System.in);
System.out.print("Enter Array Size : ");
size = scan.nextInt();
System.out.print("Enter Array Elements : ");
for(i=0; i<size; i++)
{
arr[i] = scan.nextInt();
}
System.out.print("Sorting Array using Insertion Sort Technique..\n");
for (i = 1; i < size; i++) {
temp = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = temp;
}
System.out.print("Array after Sorting is : \n");
for(i=0; i<size; i++)
{
System.out.print(arr[i] + " ");
}
}
}

Insertion Sorting in Python

The following Pythonprogram asks the user to enter the array size and array element to sort the array using the insertion sort technique, then display the sorted array on the screen:

# Python program for implementation of Insertion Sort

def insertionSort(arr):
# Traverse through 1 to len(arr)
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >=0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key

Features of Insertion Sort

There are several characteristics of Insertion Sort are discussed below:

Insertion Sort is efficient for smaller data sets but can be inefficient for larger data sets.

Insertion Sort is an adaptive algorithm means it can be used for arrays that are partially sorted appropriately.

Easy and Simple Implementation is also one of the characteristics because every beginner can learn this sorting algorithm.

The space complexity is lesser as we don't have to create extra memory other than the given array of elements that are to be sorted.

In the best case, where the array is already sorted, Time Complexity will be linear O(n).

Insertion Sort Complexity

In both the worst and average scenarios, where 'n' is the number of elements, Insertion Sort has an O(n^2) time complexity. This is because it could, in the worst case, involve nested loops for swaps and comparisons. But in the best scenario (when the list is already sorted), it has an efficient time complexity of O(n).

Since Insertion Sort doesn't need extra memory in proportion to the input size, its space complexity is O(1). Sorting in place or rearranging elements within the current array without allocating new memory. Although Insertion Sort is straightforward and appropriate for small datasets, it loses efficiency when applied to larger datasets compared to more advanced sorting algorithms like Quick Sort or Merge Sort.

Frequently Asked Questions

What is insertion sorting in C?

In C, Insertion Sorting is an algorithm that divides the array into the sorted and unsorted subarrays, where the element of the unsorted part can be inserted in the sorted part, and the process can go on in order to sort the complete array.

What is insertion sort with an example?

A straightforward sorting algorithm is the insertion sort. Each item is inserted into the appropriate position to build the sorted array one item at a time. Repeatedly putting cards in the correct order can be used to sort a deck of cards.

What is insertion sort steps?

A straightforward sorting algorithm is the insertion sort. Its steps involve repeatedly moving an element from a list's unsorted section to the appropriate spot in the sorted section.

What is the purpose of insertion sorting?

Insertion sorting is used to reorder items in an array into ascending or descending order. It accomplishes this by repeatedly placing elements in the appropriate positions.

Conclusion

Insertion sort isn’t a particularly efficient algorithm, but it is easy to understand and relatively straightforward to write up. There are a handful of different ways to implement it, and I encourage you to take the tests I provided and try to find a different way to implement it.

In this article, we discussed what Insertion sort is, The algorithm of insertion sort, The working of insertion sort, The implementation of Insertion Sort in C, C++, Java, and Python, and the characteristics of Insertion Sort.