10,757 views
2 votes
2 votes

Consider the array A[]= {6,4,8,1,3} apply the insertion sort to sort the array . Consider the cost associated with each sort is 25 rupees , what is the total cost of the insertion sort when element 1 reaches the first position of the array  ?
(A) 50
(B) 25
(C) 75
(D) 100

Source: http://quiz.geeksforgeeks.org/algorithms-insertionsort-question-4/

3 Answers

6 votes
6 votes
in first pass as 6>4,while loop will get executed which will cost 25.

at the end of that pass array would be 4 6 8 1 3.

in second pass as 8>6 while will not execute hence cost is 0.

similarly for 3rd pass while loop will get executed and 1 will be on first position so the cost is 25
total cost 25+0+25=50
0 votes
0 votes
I am also not getting this question.
0 votes
0 votes

->here if we consider cost associated with swap then answer is 25+0+25*3=100

->but if we consider the cost associated with no of iterations that is as soon as 1 is at position 1 we will stop so in that case answer is 25+0+25=50

as 25 is cost associated with each sort so for first pass there is swap operation cost is 25 for 2nd swap there is no swap so cost is 0 and for 3rd pass there is swap operation cost is 25

overall cost is 25+0+25=50

Related questions

1 votes
1 votes
0 answers
1
0 votes
0 votes
1 answer
2
LavTheRawkstar asked Jan 12, 2017
806 views
INSERTION-SORT (A, n) ⊳ A[1 . . n]for (j ← 2 to len(A) ){key ← A[ j];i ← j – 1 ; while (i 0 and A[i] key) { A[...
0 votes
0 votes
1 answer
3
2 votes
2 votes
1 answer
4
Diksha Aswal asked Jul 8, 2017
368 views
How to get Time Complexity of finding the number of inversions in an array?