Insertion sort is also very simple sorting algorithm. In this sorting we break the list in two parts.
We pick up a particular value and insert it at the appropriate place in the sorted sub list. That means during the kth iteration the element a[k] is inserted in its proper place in the sorted sub array.
Algorithm
Following are the simple steps to sort array using insert sort:
Pass 1- a[1] is inserted either before or after a[0] so that a[0] and a[1] are sorted.
Pass 2- a[2] is inserted either before a[0] or between a[0] and a[1] or after a[1] so that the elements a[0] , a[1] , a[2] are sorted.
Pass k – a[k] is inserted in proper place in the sorted sub array a[0],a[1],a[2]……,a[k-1] so that after insertion , the elements a[0], a[1],a[2],….a[k-1],a[k] are sorted.
Pass n-1 – a[n-1] is inserted in proper place in sorted sub array a[0],a[1],a[2],….a[n-2],so that after insertion, the elements a[0],a[1],a[2],……a[n-1] are sorted
Working of Insertion Sort
To understand the working of insertion sort lets take an unsorted array named a having 7 elements
pass 1: Since a[1] < a[0] , insert element a[1] before a[0] , this give the following table
pass 2: Since a[1] < a[2] , no action is performed.
pass 3: Since a[2] < a[3] , no action is performed.
pass 4: Since a[4] is less than a[0], a[1], a[2] and a[3] , therefor insert a[4] before a[0] , giving the following array.
pass 5: Since a[5] is less than a[1], a[2],a[3] and a[4] , therefor insert a[5] before a[1] and after a[0] , giving the following array.
pass 6: Since a[6] is less than a[2],a[3] and a[4] , therefor insert a[6] before a[2] and after a[1] , giving the following array.
Complexity:
How to start a blog HTML 5 JavaScript Sorting Algorithm