The GATE Grind

GATE 2026 DA – Question 49

Programming, Data Structures and Algorithms · Searching and sorting algorithms · 2 marks · Multiple select

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 N1 be the total number of comparisons done by BS on the elements of P and N2 be the total number of comparisons done by IS on the elements of P.

Which of the following options is/are correct?

  1. N1 = 10, N2 = 4
  2. N1 > N2
  3. IS on P will perform only one swap
  4. Both BS and IS on P will make at least one unnecessary comparison (i.e., comparing elements that are already in correct order)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) N1 > N2; (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)

Explanation

Bubble sort without an early exit compares $4 + 3 + 2 + 1 = 10$ pairs; with an early exit it stops after the second pass, at 7 comparisons. Insertion sort compares 2 with 1, 3 with 2 and 5 with 3 (one comparison each) and for 4 compares with 5 (swap) and then with 3, which is $1 + 1 + 1 + 2 = 5$ comparisons. So N2 is 5, not 4, and A is false. In either case $N1 > N2$, so B is true. Only the 5 and the 4 are out of order, so insertion sort does exactly one swap and C is true. Both algorithms compare many pairs that are already in order, such as (1, 2) and (2, 3), so D is true.