In this article, I am going to take you through the one of the sorting algorithms, Insertion sort step by step and perform a complete analysis of it.
In this technique, we pick an element and insert it at the appropriate position in ascending or descending order. If we have n elements we require (n-1) passes to obtain the desired result.

Algorithm

• It will be divided into two sets, One that stores sorted values and one part that stores unsorted values.
• This will proceed until there are no elements left in the unsorted list. Suppose there are n elements in the array. Initially a will be in the sorted list and the rest will be in the unsorted list.
• During each iteration of the algorithm, the first element in the unsorted list is picked up and is inserted in the appropriate position.

Consider an array with the following elements to be arranged in ascending order. In this case we have 5 elements, so we require 4 passes to get the elements in ascending order.

5 4 3 1 2

In the first pass, 4 is being compared with 5 and is swapped as its lesser than 5.
In pass 2, 4 is compared with 3. Since 3 is lesser than 4, its being swapped.
In pass 3, 3 is compared with 1 and hence getting swapped.
In the final pass, 3 is compared with 2 and is being swapped. Here the ascending ordered array is obtained.

Output

On executing the above code, the following output should be available.

Time Complexity

For n elements in the array,
In 1st pass, we have 1 comparison.
In the 2nd pass, we have 2 comparisons,
Simillarly, in kth pass, we have k-1 compariosn.
And the last pass will require (n-1) comparisons.
Therefore, total comparisons are:
f(n)=1+2+3+..+(n-2)+(n-1) = n(n-1)/2 = O(n2)
Worst case here would be O(n).

References

This site uses Akismet to reduce spam. Learn how your comment data is processed.