Insertion Sort

Assume 5 persons of different heights are visiting at your office each at 5 minutes interval and you need to make them stand according to their heights(smaller to higher). How you will do?

Below is the sequence in which person is going to visit you, 

You need to arrange above persons based on their height. 

• First “A” will visit and that is the only person present, so just tell him to stand and you don’t need to take any decision.

• Second “B” will visit, so now you have to compare “B” height with “A” height, which is smaller, so shift “A” one step back and move “B” one step ahead.

Now, you have arranged 2 persons properly.

• Now “C” entered in office, so you have to find proper position for “C” to stand.
• First you will compare “C” height with “A”, which is smaller so “A” need to be shifted one step back and “C” need to be shifted one step in front.
• Now, compare “C” height with “B”, which is higher than “B”, So stop here because you have found proper position of “C” to stand.

Now, you have arranged 3 persons properly. 

• Now “D” entered in office, so you have to find proper position for “D” to stand.
• First you will compare “D” height with “A”, which is higher so “D” is already at correct position and no need to check further because all person ahead of “A” is smaller as we kept the person in ascending order as they arrived.

Now, you have arranged 4 persons properly. 

• Now “E” entered in office, so you have to find proper position for “E” to stand.
• First you will compare “E” height with “D”, which is smaller so “D” need to be shifted one step back and “E” need to be shifted one step in front.
• Now compare “E” height with “A”, which is smaller so “A” need to be shifted one step back and “E” need to be shifted one step in front.
• Now compare “E” height with “C”, which is smaller so “C” need to be shifted one step back and “E” need to be shifted one step in front.
• Now, compare “E” height with “B”, which is higher than “B”, So stop here because we have found proper position of “E” to stand and all the person ahead of B will be smaller than “B”, so no need to check further.

Insertion sort works by shifting and putting element at its correct position in array.

Let see how it works:

• Insertion sort start’s sorting an array by picking 1st element of array. (We begin by assuming that a array with one item (position 0) is already sorted.)So now we have one sorted elements set.
• Now, we will pick 2nd element of array and compare it with sorted elements set one by one until we find correct position of 2nd element in sorted set. Elements which are higher than 2nd element are shifted one step back to make space for 2nd element. After putting 2nd element at its correct position, we have 2 elements in our sorted set. 
• Now, we will pick 3rd element of array and compare it with sorted elements set one by one until we find correct position of 3rd element in sorted set.
  Elements which are higher than 3rd element are shifted one step back to make space for 3rd element.
  After putting 3rd element at its correct position, we have 3 elements in our sorted set.
• Repeat the process until all elements are sorted.  

public class InsertionSort {
	public static void main(String[] args) {
		new InsertionSort();
	}

	public InsertionSort() {
		int[] arr = new int[] { 4, 3, 2, 10, 12, 1, 5, 6 };
		System.out.println("Before Sorting...");
		printArray(arr);
		insertionSort(arr);
		System.out.println("\nAfter Sorting...");
		printArray(arr);
	}

	private void insertionSort(int arr[]) {
		if (arr == null || arr.length == 1) {
			return;
		}
		for (int i = 1; i < arr.length; i++) {
			int temp = arr[i];
			/*
			 * Comparison starts from one step back of element on which we are
			 * working that is i. Hence j = i-1. 
			 * If the new elements that comes in i.e temp is greater than the
			 * last element with whom it needs to be compared, than temp is
			 * already at correct position. Eg. Once 4,3,2 is sorted as 2,3,4
			 * and when 10 comes in as temp, it will be compared with 4, and
			 * since 10 is greater than 4, no need to make check further and
			 * continue with next iteration.
			 */
			for (int j = i - 1; j >= 0; j--) {
				if (arr[j] > temp) {
					arr[j + 1] = arr[j];
					arr[j] = temp;
				} else {
					break;
				}
			}
		}
	}

	private void printArray(int arr[]) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}

}

• The insertion sort, unlike the other sorts, passes through the array only once.
• The insertion sort splits an array into two sub-arrays,
  • First sub-array on left side is always sorted and increases in size as the sort continues. Second sub-array is unsorted, contains all the elements yet to be inserted into the first sub-array, and decreases in size as the sort continues.
• It is more efficient than selection sort or bubble sort.
• Insertion sort is very efficient for arrays which is nearly(almost) sorted and it sorts nearly sorted array in time complexity of O(N).
• For sorting an array containing elements in descending order to ascending order, insertion sort will give poor performance and complexity will be O(N^2)
• It can sort elements as it receives it and no need of complete data initially before start sorting.