Question

Using the method introduced in class, show all intermediate steps of Insertion Sort when sorting the list

27, 11, 8, 47, 88, 71, 28, 4, 19

in increasing order. For every intermediate step, show the number of comparisons of list elements needed. Finally, give the total number of comparisons needed.

Answer 1

Steps We follow in Insertion sort

1: Iterate from start till end over the array.
2: Compare the current element to its last element
3: If the element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position right to make space for the element that we swap

We have Array as : 27, 11, 8, 47, 88, 71, 28, 4, 19

Step 1

Insert 27

Step 2

Insert 11

Compare 11 and 27 as 11 <27 so swap them

Now Array is 11 27

Comparisons = 1

Step 3

insert 8

11 27 8

We compare 8 with 27 first so shift 27 one right then we compare 8 with 11 and shift 11 also one place right

Now Array is 8 11 27

Comparisons = 2

Step 4

Insert 47

47 and 27 is compared so as 47> 27 so shift is needed

Now Array is 8 11 27 47

Comparisons = 1

Step 5

Insert 88

88 and 47 is compared so as 88> 47 so shift is needed

Now Array is 8 11 27 47 88

Comparisons = 1

Step 6

Insert 71

71 and 88 are compared so as 71 < 88 so 88 will shift one place right .

Now 71 is compared with 47 . As 71 > 47 so no shift .

Now Array is 8 11 27 47 71 88

Comparisons = 2

Step 7

Insert 28

It will be compared with 47 , 71 , 88 and all three will shift one place right

Now compare it with 27 as 28 > 27 so no shift

Now Array is 8 11 27 28 47 71 88

Comparisons = 4

Step 8

Insert 4

So as 4 has to go at first place so it is compared with each element

Now Array is 4 8 11 27 28 47 71 88

Comparisons = 7

Step 9

Insert 19

It will be compared with 47 , 71 , 88 , 27 ,28 and all will shift one place right

Now compare it with 11 as 19 > 11 so no shift

Now Array is 4 8 11 19 27 28 47 71 88

Comparisons = 6

Hence we get the Sorted Array : 4 8 11 19 27 28 47 71 88

Total Number of Comparison = 0 + 1+ 2+ 1 + 1 + 2 + 4 + 7 + 6 = 24

This is how insertion sort works and we can count number of comparisons in each step .

Thank You

If u like the answer then do Upvote it and have any doubt ask in comments