GATE DA 2026 | Python & DS | Memory Based | Question 44

Answer 1

•  

Let's break down the sorting problem step-by-step for the array A=[1,2,3,5,4] where n=5.

1. Bubble Sort (N1​)

Standard Bubble Sort (without the "early exit" optimized flag) always performs 2n(n−1)​ comparisons.

• Calculations: (5×(5−1)) ​/2 =10.

• Result: N1​=10.

2. Insertion Sort (N2​)

Insertion Sort comparisons depend on the current state of the array. We take each element (starting from the second) and compare it with the sorted elements to its left.

• Step 1 (Element 2): Compare '2' with '1'. (1 comparison). Array: [1,2,3,5,4]

• Step 2 (Element 3): Compare '3' with '2'. (1 comparison). Array: [1,2,3,5,4]

• Step 3 (Element 5): Compare '5' with '3'. (1 comparison). Array: [1,2,3,5,4]

• Step 4 (Element 4):

  • Compare '4' with '5'. (1 comparison). Since 4<5, we keep looking left.

  • Compare '4' with '3'. (1 comparison). Since 4>3, we stop.

  • Array becomes: [1,2,3,4,5]

• Total Comparisons (N2​): 1+1+1+2=5.

---

Evaluating the Statements

• A. Insertion Sort on A performs only one swap: Correct. Only the element '4' needs to be shifted (swapped) to move past '5'. Elements 1, 2, 3, and 5 were already in relative sorted order.

• B. N1​=10,N2​=4: Incorrect. As calculated above, N2​=5.

• C. N1​>N2​: Correct. 10>5.

• D. Both algorithms make at least one unnecessary comparison: Correct.

  • Bubble Sort compares 1 & 2, 2 & 3, and 3 & 5 even though they are already in order.

  • Insertion Sort compares '3' with '2' and '5' with '3' even though they are already in their correct positions.

  • so option A ,C, D is correct .