Interview Preparation Insertion Sort
From Embedded Systems Learning Academy
Revision as of 12:28, 25 November 2016 by Proj user18 (talk | contribs) (Created page with "Algorithm for implementation of insertion sort is as follows a. Start from index 1. b. compare higher index element with all the elements at smaller index. c. If element at...")
Algorithm for implementation of insertion sort is as follows
a. Start from index 1.
b. compare higher index element with all the elements at smaller index.
c. If element at smaller index number is greater than element at higer index than shift the element at smaller index towards right.
d. Store element of higher value in the last index where vacancy is created.
e. Repeating step b, c and d until the array is sorted.
For an array with n number of elements,
Best case complexity = O(n).
Average case complexity = Worst case complexity = O(n^2).
