Insertion sort algorithm for interviews by Abhishek Kothari

About the article

In this article, I am going to take you through the one of the sorting algorithms, Insertion sort step by step and perform a complete analysis of it.
In this technique, we pick an element and insert it at the appropriate position in ascending or descending order. If we have n elements we require (n-1) passes to obtain the desired result.

Algorithm

It will be divided into two sets, One that stores sorted values and one part that stores unsorted values.
This will proceed until there are no elements left in the unsorted list. Suppose there are n elements in the array. Initially a[0] will be in the sorted list and the rest will be in the unsorted list.
During each iteration of the algorithm, the first element in the unsorted list is picked up and is inserted in the appropriate position.

Consider an array with the following elements to be arranged in ascending order. In this case we have 5 elements, so we require 4 passes to get the elements in ascending order.

5 4 3 1 2

In the first pass, 4 is being compared with 5 and is swapped as its lesser than 5.
In pass 2, 4 is compared with 3. Since 3 is lesser than 4, its being swapped.
In pass 3, 3 is compared with 1 and hence getting swapped.
In the final pass, 3 is compared with 2 and is being swapped. Here the ascending ordered array is obtained.

Code

package com.algorithm;
public class InsertionSort {
void insertionSort(int inputArr[]) {
int n = inputArr.length; // getting the length
for (int j = 1; j < n; j++) // loop to traverse the array
{
int key = inputArr[j];
int i = j - 1;
while ((i > -1) && (inputArr[i] > key)) { // comparing the first element and the rest
inputArr[i + 1] = inputArr[i]; // swap if its less
i--;
}
inputArr[i + 1] = key;
}
}
/* Printing sorted array */
void printArray(int inputArr[]) {
int n = inputArr.length;
for (int i = 0; i < n; ++i) {
System.out.print(inputArr[i] + " ");
}
System.out.println();
}
public static void main(String args[]) {
InsertionSort obj = new InsertionSort(); // object creation
int inputArr[] = { 80, 15, 60, 30, 20, 90 }; // calling function with inputs.
System.out.println("Input Array before Insertion Sort.");
obj.printArray(inputArr);
obj.insertionSort(inputArr);
System.out.println("\nSorted Array after Insertion Sort.");
obj.printArray(inputArr);
}
}

package com.algorithm;

public class InsertionSort {

void insertionSort(int inputArr[]) {

int n = inputArr.length; // getting the length

for (int j = 1; j < n; j++) // loop to traverse the array

{

int key = inputArr[j];

int i = j - 1;

while ((i > -1) && (inputArr[i] > key)) { // comparing the first element and the rest

inputArr[i + 1] = inputArr[i]; // swap if its less

i--;

}

inputArr[i + 1] = key;

}

/* Printing sorted array */

void printArray(int inputArr[]) {

int n = inputArr.length;

for (int i = 0; i < n; ++i) {

System.out.print(inputArr[i] + " ");

}

System.out.println();

}

public static void main(String args[]) {

InsertionSort obj = new InsertionSort(); // object creation

int inputArr[] = { 80, 15, 60, 30, 20, 90 }; // calling function with inputs.

System.out.println("Input Array before Insertion Sort.");

obj.printArray(inputArr);

obj.insertionSort(inputArr);

System.out.println("\nSorted Array after Insertion Sort.");

obj.printArray(inputArr);

}

Output

On executing the above code, the following output should be available.

Input Array before Insertion Sort.
80 15 60 30 20 90 
Sorted Array after Insertion Sort.
15 20 30 60 80 90

Input Array before Insertion Sort.

80 15 60 30 20 90

Sorted Array after Insertion Sort.

15 20 30 60 80 90

Time Complexity

For n elements in the array,
In 1st pass, we have 1 comparison.
In the 2nd pass, we have 2 comparisons,
Simillarly, in kth pass, we have k-1 compariosn.
And the last pass will require (n-1) comparisons.
Therefore, total comparisons are:
f(n)=1+2+3+..+(n-2)+(n-1) = n(n-1)/2 = O(n2)
Worst case here would be O(n).