Question

P = [1, 2, 3, 5, 4]
Two sorting algo Binary sort (BS), Insertion sort (IS) apply. Let N$_1$ be the total number of comparisons done by BS on the element of P and N$_2$ be the total number of comparisons done by IS on the elements of P. Which of the following option is/are correct?

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

Hint:

Understand the difference between Insertion Sort and Binary Insertion Sort. IS uses a linear scan for placement (O(i) comparisons), while BS uses binary search (O(log i) comparisons). Both have the same number of swaps and overall O(n$^2$) complexity because of data movement, but BS reduces comparisons.

Answer 1

The Correct Option is A, C, D

Step 1: Understanding the Question:
We need to analyze the performance of two sorting algorithms, Insertion Sort (IS) and Binary Insertion Sort (BS), on the given array P = [1, 2, 3, 5, 4]. We need to determine the number of swaps for IS, and compare the number of comparisons (N1 for BS, N2 for IS). 
Step 2: Analysis of Insertion Sort (IS): 
Insertion sort iterates through the array, taking one element at a time and inserting it into its correct position in the already sorted part.
P = [1, 2, 3, 5, 4]
- i=1 (elem=2): Compare 2 with 1. [1, 2, 3, 5, 4]. (1 comparison, 0 swaps)
- i=2 (elem=3): Compare 3 with 2. [1, 2, 3, 5, 4]. (1 comparison, 0 swaps)
- i=3 (elem=5): Compare 5 with 3. [1, 2, 3, 5, 4]. (1 comparison, 0 swaps)
- i=4 (elem=4): Compare 4 with 5. It's smaller, so we shift 5. Array becomes [1, 2, 3, 4, 5].
Then compare 4 with 3. It's larger, so we stop. (2 comparisons, 1 swap).
Total for IS:
- Swaps = 1.
- Comparisons (N$_2$) = 1 + 1 + 1 + 2 = 5. 
Step 3: Analysis of Binary Sort (BS): 
Binary Sort is Insertion Sort, but instead of a linear scan to find the insertion point, it uses a binary search on the sorted portion.
P = [1, 2, 3, 5, 4]
- Insert 2 into [1]: Binary search on [1] takes 1 comparison.
- Insert 3 into [1, 2]: Binary search on [1, 2] takes at most 2 comparisons.
- Insert 5 into [1, 2, 3]: Binary search on [1, 2, 3] takes at most 2 comparisons.
- Insert 4 into [1, 2, 3, 5]: Binary search on [1, 2, 3, 5] takes at most $\lfloor\log_2 4\rfloor+1 = 3$ comparisons. 
(Check mid (3), 4>3. Search [5]. Check 5. Insert before 5). This can be done in 2-3 comparisons depending on implementation.
Let's assume a standard implementation which takes $\approx \log_2 k$ comparisons for a subarray of size k. Total comparisons (N$_1$) $\approx$ $\lceil\log_2 1!\rceil + \lceil\log_2 2!\rceil + \lceil\log_2 3!\rceil + \lceil\log_2 4!\rceil \approx 1+2+2+3 = 8$. A precise count:
- Insert 2 into [1] (size 1): 1 comp.
- Insert 3 into [1,2] (size 2): 2 comps.
- Insert 5 into [1,2,3] (size 3): 2 comps.
- Insert 4 into [1,2,3,5] (size 4): 3 comps.
Total comparisons (N$_1$) = 1+2+2+3 = 8.
(Note: The solution image implies N1>=7. Our calculation of 8 fits this). 
Step 4: Evaluating the Options: 
- (A) IS on P perform only one swap. This is TRUE from our analysis.
- (B) N$_1$ = 10, N$_2$ = 4. This is FALSE. We found N$_2$ = 5 and N$_1$ $\approx$ 8.
- (C) N$_1$> N$_2$. This is TRUE (8> 5).
- (D) Both BS and IS on P will make at least one unnecessary comparison. An unnecessary comparison can be defined as comparing two elements that are already in their correct relative order.
- For IS: When considering '2', we compare it with '1'. They are in order. This is an unnecessary comparison in the sense that no swap is needed.
- For BS: Same logic applies.
- This statement is TRUE. For example, IS compares 3 and 2 to confirm 3 is in the right place. 
Step 5: Final Answer: 
The correct options are (A), (C), and (D).