edited by
3,751 views
22 votes
22 votes

Consider the Insertion Sort procedure given below, which sorts an array $L$ of size $n\left ( \geq 2 \right )$ in ascending order:

begin     
    for xindex:= 2 to n do        
        x := L [xindex];
        j:= xindex - 1;
        while j > 0 and L[j] > x do
            L[j + 1]:= L[j];
            j:= j - 1;
        end {while}
        L [j + 1]:=X;
    end{for}   
end

It is known that insertion sort makes at most $n (n - 1) / 2$ comparisons. Which of the following is true?

  1. There is no input on which insertion Sort makes $n (n - 1) / 2 $ comparisons.
  2. Insertion Sort makes $n (n - 1) / 2$ comparisons when the input is already sorted in ascending order.
  3. Insertion Sort makes $n (n - 1) / 2$ comparisons only when the input is sorted in descending order.
  4. There are more than one input orderings where insertion sort makes $n (n - 1) / 2 $ comparisons.
  5. Insertion Sort makes $n (n - 1) / 2$ comparisons whenever all the elements of $L$ are not distinct.
edited by

4 Answers

Best answer
14 votes
14 votes

Option D: In the worst case, the number of comparisons for given Insertion Sort are $\frac{n(n-1)}{2}$.

Consider the set of numbers $1,2,3,4,5$. Some examples for which the number of comparisons are maximum are

  1. Descending order: $5,4,3,2,1$
  2.  $3, 5, 4, 2, 1$
  3. $3,5,4,1,2$

There is more than $1$ sequence for which the number of comparisons is maximum.

$\therefore$ Correct answer: $D$

Let us see why other options are false.

Option A: Since option D is true, option A is false.

Option B: Given Insertion Sort makes $(n-1)$ comparisons when the input is already sorted in ascending order.

Hence option B is false.

Option C: Insertion Sort makes $\frac{n(n-1)}{2}$ comparisons only when the input is sorted in descending order.

Since the word only is used, this option is false.

Option E: Insertion Sort makes $\frac{n(n-1)}{2}$ comparisons whenever all the elements of $L$ are not distinct.

Not distinct means either all the elements are same or few elements are same and few are distinct.

When elements are same, number of comparisons are $n-1$.

When few elements are same and few are distinct, number of comparisons are always less than $\frac{n(n-1)}{2}$ because while comparing same elements we don’t enter while loop. 

Hence option E is false.

Note: There can be more than $1$ sequence for maximum number of comparisons in insertion sort but maximum number of movements or swaps occur only when input is in Descending Order for this question.

edited by
13 votes
13 votes
In worst case Insertion sort will have $n(n-1)/2$ comparisons i.e. when input is sorted in descending order.

$50 \ 40 \ 30 \ 20 \ 10 \ldots n$

pass $1:\quad \ 50 \ 40 \ 30 \ 20 \ 10\ldots n$$\qquad0$ comparison

pass $2:\quad \ 40 \ 50 \ 30 \ 20 \ 10\ldots n$$\qquad1$ comparison
  .
  .
  .
  .                                                                                                                                          
pass $n:\quad n \ldots10 \ 20 \ 30 \ 40 \ 50$$\qquad n-1$ comparisons                                                         
Total $1+2+3+\ldots+n-1 = n(n-1)/2$  comparisons

Correct Answer: $C$
edited by
2 votes
2 votes
Here they have just confused with some new variable names:-

Comparing with our standard algo that given in many places i.e. CLRS

xindex => i

x => key

L[ ] => A[ ]

And we know that worst case no. of comparisons (n×n-1 /2) arise only when i/p sequence is in decreasing order .

So Ans Must be C.
1 votes
1 votes

There are more than one input orderings where insertion sort makes n (n - 1) / 2 comparisons.

 

this is false since insertion sort is stable sort.

so there can be a non monotically decreasing sequence then in this case the comparisons will  not to upto start.

Answer:

Related questions