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: Count the comparisons made by Bubble Sort.
The array is \(P = [1, 2, 3, 5, 4]\), with 5 elements. A standard bubble sort makes \((n-1)\) passes, and pass \(i\) (starting at 0) compares \((n-1-i)\) adjacent pairs.
Pass 1 compares 4 pairs: (1,2), (2,3), (3,5), (5,4). Only the last pair is out of order, so one swap happens and the array becomes [1, 2, 3, 4, 5].
Pass 2 compares 3 pairs: (1,2), (2,3), (3,4). No swaps needed.
Pass 3 compares 2 pairs: (1,2), (2,3). No swaps needed.
Pass 4 compares 1 pair: (1,2). No swap needed.
Total comparisons \(N_1 = 4 + 3 + 2 + 1 = 10\).

Step 2: Count the comparisons made by Insertion Sort.
Insertion sort scans from left to right, inserting each new element into its correct place among the already-sorted elements to its left.
\(i=1\): key = 2, compare with 1. \(1 > 2\) is false, so no shift. 1 comparison.
\(i=2\): key = 3, compare with 2. \(2 > 3\) is false, so no shift. 1 comparison.
\(i=3\): key = 5, compare with 3. \(3 > 5\) is false, so no shift. 1 comparison.
\(i=4\): key = 4, compare with 5. \(5 > 4\) is true, so shift 5 right (1 comparison, 1 swap), then compare with 3. \(3 > 4\) is false, stop (1 more comparison). This step used 2 comparisons.
Total comparisons \(N_2 = 1 + 1 + 1 + 2 = 5\).

Step 3: Check option (A).
Option (A) claims \(N_1 = 10, N_2 = 4\). We found \(N_1 = 10\) but \(N_2 = 5\), not 4, so option (A) is wrong.

Step 4: Check option (B).
\(N_1 = 10\) and \(N_2 = 5\), so \(N_1 > N_2\) holds. Option (B) is correct.

Step 5: Check option (C).
Looking at the insertion sort trace in Step 2, the only place data actually moved was at \(i = 4\), where 5 was shifted one place to the right to make room for 4. That is the single swap in the whole run, so option (C) is correct.

Step 6: Check option (D).
In bubble sort's first pass, the comparisons (1,2), (2,3), and (3,5) all compare elements that are already in the correct relative order, so they are unnecessary. Similarly, insertion sort's comparisons at \(i=1,2,3\) (1 vs 2, 2 vs 3, 3 vs 5) compare elements already in order. Both algorithms make at least one unnecessary comparison, so option (D) is correct.

Final Answer:
The correct options are (B), (C), and (D). \[ \boxed{N_1 = 10,\ N_2 = 5,\ \text{(B), (C), (D) are correct}} \]