Question

Consider the problem of sorting the given array in ascending order:

\(P = [1, 2, 3, 5, 4]\)

Consider two sorting algorithms Bubble Sort (BS) and Insertion Sort (IS).

Let \(N_1\) be the total number of comparisons done by BS on the elements of \(P\) and \(N_2\) be the total number of comparisons done by IS on the elements of \(P\).

Which of the following options is/are correct?

• A. \(N_1 = 10, N_2 = 4\)
• B. \(N_1 > N_2\)
• C. IS on P will perform only one swap
• D. Both BS and IS on P will make at least one unnecessary comparison (i.e., comparing elements that are already in correct order)

Hint:

Trace both algorithms step by step on P = [1, 2, 3, 5, 4] and count every comparison made, including the ones between elements already in the right order.

Answer 1

The Correct Option is B, C, D

Step 1: Set up the problem.
We have $P = [1, 2, 3, 5, 4]$, an array of 5 elements that is sorted except for the last two entries, which are swapped.

Step 2: Bubble sort comparison count.
A textbook bubble sort with no early-exit check always compares every adjacent pair in every pass, no matter how sorted the array already is. For $n = 5$ elements it runs 4 passes with $4, 3, 2, 1$ comparisons respectively.
$N_1 = 4+3+2+1 = 10$, which is just the sum of the first $(n-1)$ natural numbers, $\binom{n}{2} = \binom{5}{2} = 10$.

Step 3: Insertion sort comparison count.
Insertion sort only compares an element with its immediate left neighbor until it finds the correct slot, so its comparison count depends on how out of place the elements are.
Position 2 (value 2): 1 comparison against 1, no shift.
Position 3 (value 3): 1 comparison against 2, no shift.
Position 4 (value 5): 1 comparison against 3, no shift.
Position 5 (value 4): compares against 5 first (comparison 1, shift happens), then against 3 (comparison 2, stop).
$N_2 = 1+1+1+2 = 5$

Step 4: Evaluate each option against these counts.
(A) says $N_1=10, N_2=4$: the $N_1$ part is right but $N_2$ should be 5, so this option fails.
(B) says $N_1 > N_2$: $10 > 5$ holds, so this option is true.
(C) says insertion sort makes only one swap: tracing the run above, the only actual element movement is the single shift of 5 at position 5, so this is true.
(D) says both algorithms make at least one unnecessary comparison: bubble sort keeps comparing already-ordered pairs like (1,2) in every pass, and insertion sort compares 1 with 2, 2 with 3, and 3 with 5, all already-ordered pairs, so this is also true.

Step 5: A quick sanity check on why the counts differ.
Bubble sort's inner loop shrinks by exactly one comparison every pass regardless of how the data looks, since it always walks the full unsorted portion of the array, so its total is fixed by the array length alone at $\binom{5}{2}=10$. Insertion sort, on the other hand, only compares as far left as it needs to place the current key, so a nearly-sorted array like this one lets it finish with far fewer comparisons. That is exactly why $N_1=10$ is much larger than $N_2=5$ here, even though both algorithms sort the same five-element array.

Final Answer:
Options (B), (C) and (D) are correct. \[ \boxed{\text{(B), (C), (D)}} \]