Insertion Sort in Python class 11 with important examples

Insertion Sort in Python with example program

What is Insertion Sort in Python?

Insertion sort is simple sorting algorithm. It works in the same way as we (teachers) arranges answer sheets of students according to their roll number. This algorithms simply divides the list into two parts ie sorted (left side) and unsorted(right side). It simply pick up the item from right side and place them on left side according to their value.

Steps of Insertion Sort in python for increasing order :

1. It start from second element and compare it with first element , if second element is smaller then swapping will take place.
2. Now it will compare third element with second element (if third element is smaller then swapping takes place) and first element ( if third element is smaller then swapping takes place)
3. Now it will compare fourth element with third element (if fourth element is smaller then swapping takes place), with second element ( if second element is smaller then swapping takes place) and with first element ( if first element is smaller then swapping takes place )

The above process will continue till all the elements sorted.

Let us understand with an example :

Suppose we have the following random number in a list L.

L = [78, 56, 68, 42, 28, 36]

First Pass of Insertion Sort in python :

In first comparison, it compare second element (56) with first element (78) (since second element is smaller so swapping takes place) and list will become as shown below :

L = [56, 78, 68, 42, 28, 36]

Second Pass of Insertion Sort in python :

Current Status : L = [56, 78, 68, 42, 28, 36]

In first comparison, it compare third element (68) with second element (78) (Since third element is smaller so swapping takes place) and list will become as shown below :

L = [56, 68, 78, 42, 28, 36]

In second comparison, it will compare second element (68) with first element (56) (since second element is bigger so no swapping takes place) and list will become as shown below :

L = [56, 68, 78, 42, 28, 36]

Third Pass of Insertion Sort in python :

Current Status : L = [56, 68, 78, 42, 28, 36]

In first comparison, it compare fourth element (42) with third element (78) (Since fourth element is smaller so swapping takes place) and list will become as shown below :

L = [56, 68, 42, 78, 28, 36]

In second comparison, it will compare third element (42) with second element (68) (since third element is smaller so swapping takes place) and list will become as shown below :

L = [56, 42, 68, 78, 28, 36]

In third comparison, it will compare second element (42) with first element (56) (since second element is smaller so swapping takes place) and list will become as shown below :

L = [42, 56, 68, 78, 28, 36]

Fourth Pass of Insertion Sort in python :

Current Status : L = [42, 56, 68, 78, 28, 36]

In first comparison, it compare fifth element (28) with fourth element (78) (Since fifth element is smaller so swapping takes place) and list will become as shown below :

L = [42, 56, 68, 28, 78, 36]

In second comparison, it will compare fourth element (28) with third element (42) (Since fourth element is smaller so swapping takes place) and list will become as shown below :

L = [42, 56, 28, 68, 78, 36]

In third comparison, it will compare third element (28) with second element (56) (since third element is smaller so swapping takes place) and list will become as shown below :

L = [42, 28, 56, 68, 78, 36]

In fourth comparison, it will compare second element (28) with first element (42) (since second element is smaller so swapping takes place) and list will become as shown below :

L = [28, 42, 56, 68, 78, 36]

Fifth Pass of Insertion Sort in python :

Current Status : L = [28, 42, 56, 68, 78, 36]

In first comparison, it compare sixth element (36) with fifth element (78) (Since sixth element is smaller so swapping takes place) and list will become as shown below :

L = [28, 42, 56, 68, 36, 78]

In second comparison, it compare fifth element (36) with fourth element (68) (Since fifth element is smaller so swapping takes place) and list will become as shown below :

L = [28, 42, 56, 36, 68, 78]

In third comparison, it compare fourth element (36) with third element (56) (Since fourth element is smaller so swapping takes place) and list will become as shown below :

L = [28, 42, 36, 56, 68, 78]

In fourth comparison, it compare third element (36) with second element (42) (Since third element is smaller so swapping takes place) and list will become as shown below :

L = [28, 36, 42, 56, 68, 78]

In fifth comparison, it compare second element (36) with first element (28) (Since second element is bigger so no swapping takes place) and list will become as shown below :

L = [28, 36, 42, 56, 68, 78]

NOTE : Since there are 6 elements in the list so maximum covering (6 – 1 =) 5 passes the list will be sorted.

Insertion sort in python

Insertion sort program

Q1. Write a program to arrange the list in increasing order using insertion sort.

L =  [78, 56, 68, 42, 28, 36]

n=len(L)

for i in range(1,n):

     for j in range(i,0,-1):

         if L[j] < L[j-1]:

               L[j], L[j-1] = L[j-1], L[j]
         else:
               break:
         print(L) # to show result after every pass

     print( )
  
print(L)

Q2. Write a program to arrange the list in decreasing order using insertion sort.

L =  [78, 56, 68, 42, 28, 36]

n=len(L)

for i in range(1,n):

     for j in range(i,0,-1):

         if L[j] > L[j-1]:

               L[j], L[j-1] = L[j-1], L[j]
         else:
               break:
         print(L) # to show result after every pass

     print( )
  
print(L)

Q3. Write the status of given List after first pass of insertion sort for arranging in increasing order. L = [34, 23, 12, 67, 87, 34]

Ans. After first pass the result will be : [23, 34, 12, 67, 87, 34]