1.

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 14 7 9 2 12 4 7 9 11 2 4 7 9(b) 9 7 4 1 29 7 1 2 49 1 2 4 71 2 4 7 9(c) 7 4 2 1 94 2 1 9 72 1 9 7 41 9 7 4 2(d) 7 9 4 2 12 4 7 9 14 7 9 2 11 2 4 7 9I 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»

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.


Discussion

No Comment Found

Related InterviewSolutions