Insertion Sort - Sorting Algorithms

Insertion sort algorithm - Sorting Algorithms

Insertion sort is a very simple sorting algorithm where we divide the whole array into two sub arrays. Out of these two sub arrays one is always sorted and another one is unsorted. In each iteration we take one element from the unsorted subarray and put it in the sorted sub array at the right place so that sorted sub array remains sorted even after inserting the new element in it.

Initially the length of sorted sub array will be 1 because an array with one element is always sorted and when we start placing the elements of unsorted sub array in the sorted sub array the length of sorted sub array will keep increasing and will reach the length of the entire array when all the elements are sorted.

Let’s try to understand Insertion sort with the help of an example -
Suppose we have an integer array - {11,2,11,3,21,2,34,2,5,6,76,77,8}

Suppose 11 is in the sorted array and rest of the elements are part of unsorted subarray.
Now we will start from index 1 and insert the element ‘2’ in the sorted subarray.
To insert the new element 2 in the sorted sub array at the correct position we will compare it with elements already in the sorted array and insert it at the correct position.
Because 2 is less than 11 so we will swap these two elements in the sorted sub array.
We will repeat the same procedure for all the elements in the unsorted sub array until the whole array is sorted.

Let’s take a look at the java code implementation for Insertion sort of this array -

package algo.sorting;

public class InsertionSort {
public static void main(String args[]) {
  int[] arr = new int[] { 11, 2, 11, 3, 21, 2, 34, 2, 5, 6, 76, 77, 8 };
  
  System.out.println("Unsorted Array - ");
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
  
  arr = sort(arr);
  
  System.out.println();
  System.out.println("Sorted Array After Insertion Sort - ");
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
 }

 public static int[] sort(int[] arr) {

  int n = arr.length;

  for (int i = 0; i < n - 1; i++) {
   for (int j = i + 1; j > 0; j--) {
    if (arr[j] < arr[j - 1]) {
     int temp = arr[j];
     arr[j] = arr[j - 1];
     arr[j - 1] = temp;
    }

   }
  }
  return arr;
 } 
}

Unsorted Array - 
11 2 11 3 21 2 34 2 5 6 76 77 8 
Sorted Array After Insertion Sort - 
2 2 2 3 5 6 8 11 11 21 34 76 77