Difference between revisions of "Interview Preparation Insertion Sort"
From Embedded Systems Learning Academy
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...") |
Proj user18 (talk | contribs) |
||
| Line 10: | Line 10: | ||
e. Repeating step b, c and d until the array is sorted. | e. Repeating step b, c and d until the array is sorted. | ||
| + | |||
| + | '''Code Snippet''' | ||
| + | <pre> | ||
| + | for(l = 1 ; l < Elecount ; l++) | ||
| + | { | ||
| + | temp = array[l]; | ||
| + | while(l > 0 && array[l-1] >temp) | ||
| + | { | ||
| + | array[l] = array[l-1]; | ||
| + | l = l - 1; | ||
| + | } | ||
| + | array[l] = temp; | ||
| + | }</pre> | ||
| + | |||
For an array with n number of elements, | For an array with n number of elements, | ||
Latest revision as of 13:13, 25 November 2016
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.
Code Snippet
for(l = 1 ; l < Elecount ; l++)
{
temp = array[l];
while(l > 0 && array[l-1] >temp)
{
array[l] = array[l-1];
l = l - 1;
}
array[l] = temp;
}
For an array with n number of elements,
Best case complexity = O(n).
Average case complexity = Worst case complexity = O(n^2).
