Question

Explain Insertion Sort.

Answer 1

Insertion sort is another sorting algorithm that can arrange elements of a given list in ascending or descending order. Like Selection sort, in Insertion sort also, the list is divided into two parts - one of sorted elements and another of unsorted elements. Each element in the unsorted list is considered one by one and is inserted into the sorted list at its appropriate position. In each pass, the sorted list is traversed from the backward direction to find the position where the unsorted element could be inserted. Hence the sorting method is called insertion sort. 

In pass 1, the unsorted list has n-1 elements and the sorted list has a single element (say element s). The first element of the unsorted list (say element e) is compared with the element s of sorted list. If element e is smaller than element s, then element s is shifted to the right making space for inserting element e. This shifting will now make sorted list of size 2 and unsorted list of size n-2. 

In pass 2, the first element (say element e) of unsorted list will be compared with each element of sorted list starting from the backward direction till the appropriate position for insertion is found. The elements of sorted list will be shifted towards right making space for the element e where it could be inserted.

This continues till all the elements in unsorted lists are inserted at appropriate positions in the sorted list. This results into a sorted list in which elements are arranged in ascending order.

Figure demonstrates the working of the insertion sort to arrange a list in ascending order.

Comparisons done in different passes of Insertion sort

Let us consider that numList is a list consisting of n elements. Algorithm sorts the list numList in ascending order using insertion sort technique.

Algorithm : Insertion Sort

INSERTIONSORT( numList, n) 

Step 1: SET i=1 

Step 2: WHILE i< n REPEAT STEPS 3 to 9 

Step 3:    temp = numList[i] 

Step 4:    SET j = i-1 

Step 5: WHILE j> = 0 and numList[j]>temp,REPEAT STEPS 6 to 7 

Step 6:             numList[j+1] = numList[j] 

Step 7:             SET j=j-1 

Step 8: numList[j+1] = temp #insert temp at position j 

Step 9: set i=i+1

Program : Implementation of insertion sort using Python.

def insertion_Sort(list3): 

  n= len(list3) 

  for i in range(n): # Traverse through all elements 

       temp = list3[i] 

        j = i-1 

        while j >=0 and temp< list3[j] : 

                  list3[j+1] = list3[j] 

                  j = j-1 

         list3[j+1] = temp 

numList = [8, 7, 13, 1, -9, 4] 

insertion_Sort(numList) 

print (“The sorted list is :”) 

for i in range(len(numList)): 

     print (numList[i], end=" ") 

Output: 

  The sorted list is : 

  -9 1 4 7 8 13