Insertion Sort Algorithm - The Coding Shala

Last Updated: 20-Jan-2021

Home >> Algorithms >> Insertion Sort

 In this post, we will learn what is Insertion Sort Algorithm and how it works. We will write a Java program for Insertion Sort.

Insertion Sort Algorithm

Insertion sort is an algorithm to sort a given array. The Insertion sort works on the principle of inserting an element at a particular position, hence known as Insertion Sort.

Working of Insertion Sort Algorithm

The Insertion sort works as follows:

• step 1. We take an element as key starts from index 1.
• Step 2. we compare all previous elements from the key element index if elements are greater than the key we move them to the next index.
• Step 3. At last, we insert a key at the index where all the previous elements are less than or equals to the key.

Here is an example of the Insertion sort algorithm:

Array ->   17 25 31 13 2

key 25

   17 25 31 13 2

key 31

   17 25 31 13 2

key 13

   17 25 31 31 2     -> 31 is bigger than key

   17 25 25 31 2    -> 25 is bigger than key

   17 17 25 31 2    -> 17 is bigger than key

insert key at index 0

   13 17 25 31 2

key 2

  follow same steps

final sorted array ->  2 13 17 25 31

Time Complexity of Insertion Sort

The time complexity of Insertion sort in the worst case is O(n^2). In the worst case, we have to compare all the n elements with all other n elements.

The time complexity of Insertion sort in Best Case is O(N). if we pass a sorted array still we need to check for all the n elements.

The time complexity of the Insertion sort in the Average case is O(N^2).

Insertion Sort Algorithm Java Program

The following is the Java Program of Insertion Sort Algorithm:

import java.util.Arrays;

//quick sort
//the coding shala

class Main{
	
	public static void insertion_sort(int[] input) {
		for(int i = 1;i<input.length; i++) {
			int j = i-1;
			int key = input[i];
			while(j>=0 && input[j]>key) {
				input[j+1] = input[j];
				j--;
			}
			input[j+1] = key;
		}
	}
	
	public static void main(String[] args) {
		int[] input = {1,5,3,2,8,7,6,4};
		int len = input.length;
		insertion_sort(input);
		for(int i=0;i<len;i++) {
			System.out.print(input[i]+" ");
		}
	}
}

Other Posts You May Like

• Counting Sort Algorithm
• Bucket Sort Algorithm
• Bubble Sort Algorithm
• Binary Search Algorithm
• The Big O Notation

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.