What is Insertion Sort?

 

Introduction

When we need to perform sorting on a list of elements then Insertion Sort is one of the basic algorithms which can be used. It\’s simple but as we will see it\’s not very efficient.

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists. –Wiki

It\’s quite similar to the way we sort playing cards in our hand. It involves comparison and movement for each of the elements. It uses two loops. That\’s the reason worst case complexity is O(N²) (you can read about “Big O” notation here). The best case scenario means that the list is already sorted. So we only perform comparison and no movements. That gives us a time complexity of O(N).

Let\’s look at the Algorithm

Suppose we have a list of numbers  4,2,3,5,1,7 and we want to sort these.

• Put elements in an Array. Say array name is input. Code : int input = {4,2,3,5,1,7};
• Start with the second index i.e. input[1] which has a value 2. Let\’s denote this as \”current_number\”.
• Run a loop in reverse.
• Compare current_number with each of the numbers prior to it. If it\’s less than any then shift or move the element to right. At the end of this iteration we will find a place for current_number.
• Repeat this Procedure for all elements in the Array.

The C Program below will help you understand this better.

#include<stdio.h>

/*
	@author Ankur
	date March 31, 2018
	Simple C Program to illustrate insertion Sort
*/

void printList(int input[], int size);

int main(){
	/*Assume the following list of numbers that needs to be sorted*/
	int input[] = {4,3,5,2,1,6};
	int size = sizeof(input) / sizeof(input[0]);
	printList(input, size);
	printf(\"Perform Insertion Sort \\n\");
	
	/*This loop performs Insertion Sort*/
	for(int i=1;i<size;i++){
		int number = input[i];
		int k = i;
		for(int j=(i-1);j>=0;j--){
			if(number < input[j]){
				input[j+1] = input[j];
				k=j;
			}
		}
		if(k != i){
			input[k] = number;
		}
	}
	
	printList(input, size);
	
	return 0;
}

void printList(int *p, int size){
	printf(\"Print the List \\n\");
	for(int i = 0;i<size;i++){
		printf(\"%d \",*p);
		p++;
	}
	printf(\"\\n\");
}

I hope this short introduction helped you understand Insertion Sort.