Insertion Sort in Java

Insertion sort is based on the idea that one element from the input elements is consumed in each iteration to find its position to which it belongs in a sorted array.

The java code snippet for Insertion sort is as below

public  void insertionSort(int arr[]) {
int size= arr.length;
for (int i = 1; i <= size-1; i++) {
  int key = arr[i];
   int j = i - 1;
   while (j >= 0 && key < arr[j]) {
    //swap function
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
          }
    }
}

Consider the following array which is unsorted with 5 elements

Unsorted Array

Now we are going to Sort the above array in ascending order

Rules…

1. As per Insertion Sort, ‘Sorted’ means all elements to the left of the key are smaller than the key
2. Whenever the key is found to be less than the element to its left, The key and the element are swapped

As per Rule 1, The first element 5 is considered to be auto sorted as there is no element to the left of 5 which is greater than 5 (In fact, No elements are there to the left of 5 to consider, 5 being the first element )

Now, The insertion sort begins with the second element, The element with index 1.

The outer loop variable is i

The outer loop is going to iterate from the second element which is at index 1 to the last element which is at index [size-1]=4

The inner loop variable is j

The inner loop is going to iterate count down through the elements with index from i-1 to 0

Now let's begin…

Iteration 1 of the outer loop

The Array Before Iteration 1 of the outer loop

The Key is the element at index 1 which is 1

Now We are going to apply the insertion sort algorithm and make the element at position 1 be ‘Sorted’ [Refer Rule 1]

The swap function is called and the positions of 5 and 1 would be swapped such that the element to the left of 5 is less than it

The Array After Iteration 1 of the outer loop

Iteration 2 of the outer loop

The Array Before Iteration

The Key is the element at index 2 which is 4

Now, We are going to apply the insertion sort algorithm and make the element at position 2 be ‘Sorted’ [Refer to Rule 1]

The elements to be considered to make it Sorted are at indexes 1 and 0[values of j]

Now let's apply insertion sort

Iteration 1 of the inner loop

The Array After Iteration 1 of the inner loop

Iteration 2 of the inner loop

There will not be any change in array as the swap function is not called

Now the element at position 2 is considered to be sorted

The Array after Iteration 2 of the outer loop

Iteration 3 of the outer loop

The Array Before iteration

The Key is the element at index 3 which is 2

Now We are going to apply the insertion sort algorithm and make the element at position 3 be ‘Sorted’ [Refer to Rule 1]

The elements to be considered to make it Sorted are at indexes 1,2 and 0[values of j]

Now let’s apply insertion sort

Iteration 1 of the inner loop

The Array After Iteration of the inner loop

Iteration 2 of the inner loop

The Array After Iteration of the inner loop

Iteration 3 of the inner loop

There will not be any change in array as the swap function is not called

Now the element at position 3 is considered to be sorted

The Array after Iteration 3 of the outer loop

Iteration 4 of the outer loop

The Array Before iteration

The Key is the element at index 4 which is 3

Now We are going to apply the insertion sort algorithm and make the element at position 4 be ‘Sorted’ [Refer to Rule 1]

The elements to be considered to make it Sorted are at indexes 3,2,1 and 0[values of j]

Now let’s apply insertion sort

Iteration 1 of the inner loop

The Array After Iteration of the inner loop

Iteration 2 of the inner loop

The Array After Iteration of the inner loop

Iteration 3 of the inner loop

There will not be any change in array as the swap function is not called

Now the element at position 4 is considered to be sorted

Iteration 4 of the inner loop with j value 0 would be skipped the second condition key < arr[j] of the below while loop becomes FALSE

while(j >= 0 && key <  arr[j])

The Array after Iteration 4 of the outer loop

which is the sorted Array!

Happy Reading!