Insertion Sort

Problem Statement:
    Implement and Discuss Insertion Sort

Solution:

Insertion Sort is one of the basic sorting techniques , which is simple but inefficient in sorting large amount of data as compared to Quick Sort, Merge Sort , Heap Sort etc ..

However Insertion sort has a number of advantages:

1. Adaptive: i.e. efficient for data sets that are already substantially sorted.
           Time Complexity : O(n+d) , where d is the number of inversions.
2. Stable: does not change the relative order of elements with equal keys
3. In-Place : no additional space required.
4. Online : can sort as it receives the data.
5. More efficient than other quadratic algorithms O(n^2) like , Selection Sort and Bubble Sort,
     best case is O(n) for insertion sort and worst case is O(n^2)
     
Humans usually sort the deck of cards using insertion sort.

Concept Involved:
   For every iteration the element picked is inserted into its correct position in the already sorted array, for N element each element is picked and placed to its correct position. 

Full Source Code: LINK


Code Implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

/** * Insertion Sort Subroutine */ public int[] insertionSort(int[] arr) { int size = arr.length; for(int i=1;i<size;i++){ int j=i; int num=arr[i]; while(j>0 && arr[j-1] > num){ arr[j]=arr[j-1]; j--; } arr[j]=num; } return arr; }

Steps involved in sorting the given sequence:
   Sequence : {3, 7, 4, 9, 5, 2, 6, 1}
 

Fig: Sorting of 30 element array

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 5 7 9 2 6 1

2 3 4 5 7 9 6 1

2 3 4 5 6 7 9 1

1 2 3 4 5 6 7 9

Below is another graphical representation of intermediate step
of insertion sort.

Fig: Steps involved in Insertion Sort

References: Wikipedia
Try writing code for insertion sort by yourself
Please comment and post your suggestions.

Happy Coding!! :)