Given array:
\[
P = [1,2,3,5,4]
\]
Only the last two elements are misplaced.
Number of elements:
\[
n = 5
\]
Bubble Sort:
For standard Bubble Sort (without early stopping), the total number of comparisons is
\[
N_1 = \frac{n(n-1)}{2}
\]
\[
N_1 = \frac{5 \cdot 4}{2} = 10
\]
Insertion Sort:
We count comparisons pass by pass.
\[
[1,2,3,5,4]
\]
- \(i=1\): compare \(2\) with \(1\) → 1 comparison
- \(i=2\): compare \(3\) with \(2\) → 1 comparison
- \(i=3\): compare \(5\) with \(3\) → 1 comparison
- \(i=4\): compare \(4\) with \(5\) → 1 comparison
- \(i=4\): compare \(4\) with \(3\) → 1 comparison
Total comparisons:
\[
N_2 = 1 + 1 + 1 + 2 = 5
\]
Thus,
\[
N1 = 10, \quad N2 = 5
\]
Checking options:
(A)
\[
N1 = 10, \quad N2 = 4
\]
False since
\[
N_2 = 5
\]
(B)
\[
N1 > N2
\]
Since
\[
10 > 5
\]
True.
(C) Insertion Sort performs only one swap.
There is exactly one inversion:
\[
(5,4)
\]
Element \(4\) shifts once, so only one swap.
Small technical note: In the standard implementation of insertion sort, we usually shift elements rather than literally swap them. But this question is clearly using the exchange/swap interpretation, so C is intended to be correct.
The question is likely using "swap" loosely to mean "one element movement/exchange," which is common in many textbooks and exam-prep material that don't rigorously distinguish the two terms.
True.
(D) Both BS and IS make at least one unnecessary comparison.
Bubble Sort compares already sorted pairs like \((1,2)\), \((2,3)\), etc.
Insertion Sort also compares already sorted elements before reaching the misplaced element.
True.
Final Answer:
\[
\boxed{(B), (C), (D)}
\]
Shortcut Tricks to Save Time in This Type of Questions:
1.Bubble Sort comparisons (without early break):
\[
\frac{n(n-1)}{2}
\]
2. Insertion Sort comparisons:
\[
\text{Comparisons} = \text{Number of inversions} + (n-1)
\]
3.If array is nearly sorted:
\[
\text{ Insertion Sort is close to linear time.}
\]
