Question

Consider an array of length 5, arr[5] = {9,7,4,2,1}. What are the steps of insertions done while running insertion sort on the array?

(a) 7 9 4 2 1   

4 7 9 2 1   

2 4 7 9 1   

1 2 4 7 9

(b) 9 7 4 1 2   

9 7 1 2 4   

9 1 2 4 7   

1 2 4 7 9

(c) 7 4 2 1 9   

4 2 1 9 7    

2 1 9 7 4   

1 9 7 4 2

(d) 7 9 4 2 1    

2 4 7 9 1   

4 7 9 2 1    

1 2 4 7 9

I have been asked this question at a job interview.

I would like to ask this question from Insertion sort in section Sorting of Data Structures & Algorithms II

Answer 1

Right option is (a) 7 9 4 2 1   

4 7 9 2 1   

2 4 7 9 1   

1 2 4 7 9

Easiest explanation - The steps performed while running insertion sort on given array are:

Initial : 9 7 4 2 1 key = 7

                 7 9 4 2 1 key = 4

                  4 7 9 2 1 key = 2

                  2 4 7 9 1 key = 1

                  1 2 4 7 9

In each step, the key is the element that is compared with the elements present at the left side to it.