MadeEasy Test Series: Algorithms - Sorting

Question

Consider the following scenario during insertion sort when the array looks like the following:

{25,75,95,125,80,5,10}

The number of comparisons that it will further take for the array to be completely sorted are______?

Comments

here it is given that some part of the array is already sorted since it says "scenario during insertion sort". Now it asks for further comparisons that are needed for the array to be sorted. Here till 125 the array is sorted and then the remaining part from 80 to 10 isnt sorted. So should we consider the comparisons starting from 80 or should we also take into consideration the comparisons needed for the first part of the array till 125?

According to me, we should take into consideration the comparisons only from 80 onwards since question asks for further number of comparisons needed and not total number of comparisons. But the solution is given by considering the comparisons for the first half of the array also.

---

Somoshree Datta 5 we have to compare for first four elements  we know that they are in sorted order yepp condition is going to false but atleast we are comparing

---

@Deepanshu but question asks for "further comparisons that are needed". Then why do we need to consider total number of comparisons?

---

17??

---

Somoshree Datta 5  in insertion sort algo we always start from comparing 1st and 2nd element.

they ask from comparisons from further still we start from element 1st and 2nd because we dont which further comparisons they are talking about .

if they say that we run loop four times and after that find comparisons then you are right . but they dont say anything about what further .

we know just by seeing example that first four are sorted how will computer know or our algo now that first four are sorted

---

@Deepanshu Yes now it got cleared..Thank u :)

---

The question uses the word "during" insertion sort, "further" comparisons and then the solution doesn't consider them!! :/

Also it is not clear as up to which element comparison has been done. I mean if the initial array was like {75,25,95,125,80,5,10} then 1st iteration will take key as 25 and make the array like  {25,75,95,125,80,5,10} (i.e. the one given in the question). If this is the case then we have to start solving by taking key=95.

Though at first I also assumed key to be 80.

To me it is not a well framed question :/

---

@MiniPanda Yes they shouldnt have mentioned the line "further comparisons needed"..instead just asking the number of comparisons required for insertion sort on the given array wouldn't have led to any confusion!

Answer 1

Getting 17 as the answer. Questioner should confirm

Comments

ya 17 is the answer

Answer 2

It is given that “The number of comparisons that it will further take for the array to be completely sorted are”

Hence it means that some of the array was already sorted (first 4 elements).

Hence I think we need to answer the no of comparison for the last unsorted elements,