Insertion sort
Insertion sort is based on the idea of inserting a record or records into an existing sorted file. To insert a record, we are required to find the proper place where the insertion is to be made, and then the record will be inserted.
The process will be as follows
Suppose we have an array A with “n” elements. A[0],A[1].. . . A[n-1].
Step 1: element A[0] is considered it is alone so it is sorted.
Step 2: element A[1] is considered. This element is either inserted before A[0] or after A[0] in such a manner that the elements A[0] and A[1] are sorted.
Step 3: element A[2] is considered. This elements is either placed before A[0] or between A[0] and A[1] or after A[1] in such a manner that the elements A[0],A[1],A[2] are sorted.
And so on.
How Insertion Sort Works?
Consider the following elements are to be sorted in ascending order-
6,2,11,7,5
Insertion sort works as-
Firstly,
• It selects the second element (2).
• It checks whether it is smaller than any of the elements before it.
• Since 2 < 6, so it shifts 6 towards right and places 2 before it.
• The resulting list is 2, 6, 11, 7, 5.
Secondly,
• It selects the third element (11).
• It checks whether it is smaller than any of the elements before it.
• Since 11 > (2, 6), so no shifting takes place.
• The resulting list remains the same.
Thirdly,
• It selects the fourth element (7).
• It checks whether it is smaller than any of the elements before it.
• Since 7 < 11, so it shifts 11 towards right and places 7 before it.
• The resulting list is 2, 6, 7, 11, 5.
Fourthly,
• It selects the fifth element (5).
• It checks whether it is smaller than any of the elements before it.
• Since 5 < (6, 7, 11), so it shifts (6, 7, 11) towards right and places 5 before them.
• The resulting list is 2, 5, 6, 7, 11.
As a result, sorted elements in ascending order are-
2, 5, 6, 7, 11
Advantages:
* It is easy to learn
* Few lines of code
* Insertion sort is efficient for small data sets.
* It does not change the relative order of elements with equal keys.
Disadvantages:
* It is not effective for large number of sorting elements.
* It needs a large number of element shifts
* If we increase the number of elements then the performance of the program would be slow.
