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
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala