Python Tutorial @ Home

# Python Searching and Sorting|Insertion sort

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