+1 vote
in Data Structures & Algorithms II by (110k points)
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

1 Answer

+1 vote
by (614k points)
selected by
 
Best 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.

Related questions

Welcome to TalkJarvis QnA, a question-answer community website for the people by the people. On TalkJarvis QnA you can ask your doubts, curiosity, questions and whatever going in your mind either related to studies or others. Experts and people from different fields will answer.

Categories

...