Insertion Sort

Insertion Sort

---

Given a array of integers, Sort it using Insertion sort. Lets understand what is the input and the expected output.

Example

---

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.

Same logic we will use in Insertion sort.

Algorithm

---

Insertion Sort is very basic and easy sorting algorithm to understand and implement.

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

Lets 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.  

Complexity

---

1. The insertion sort, unlike the other sorts, passes through the array only once. 
2. 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.

3. Insertion sort is efficient for (quite) small data sets.
4. It is more efficient than selection sort or bubble sort.
5. 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))

6. It is Stable sort; i.e., does not change the relative order of elements with equal keys.
7. It is In-place sort; i.e., only requires a constant amount O(1) of additional memory space
8. It can sort elements as it receives it and no need of complete data initially before start sorting.
    (Online).

Java Program for Insertion Sort

---

package javabypatel;

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

 public InsertionSort() {
  int[] arr=new int[]{1,9,4,10,0};

  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<2){
   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.
   int j=i-1; 
   
   //Compare elements till we not found element higher than temp or all element are compared.
   while( j >= 0 && arr[j] > temp){
    arr[j+1] = arr[j];
    j--;
   }
   arr[j+1]=temp;   
  }
 }

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

You may also like to see

---

Merge Sort

Heap Sort

Selection Sort

Bubble Sort

Quick Sort

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.