# 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?

+1 vote
757 views
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 vote
by (687k points)
selected by

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.

+1 vote
+1 vote
+1 vote
+1 vote