IAE Academy

GATE 2026 DA Q.49: solution and answer

GATE 2026 · DAQ.49 · 2 marks · MSQ

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. (A)

    N1 = 10, N2 = 4

  2. (B)

    N1 > N2

  3. (C)

    IS on P will perform only one swap

  4. (D)

    Both BS and IS on P will make at least one unnecessary comparison (i.e., comparing elements that are already in correct order)

See the question in the paper
GATE 2026 DA question 49Tap to open full size

Answer and solution

ANSWER

The correct options are (B), (C) and (D).

Official answer: B, C, DSource: Official answer key, GATE 2026 DA (IIT Guwahati)

  1. Insertion sort (IS) on P = [1, 2, 3, 5, 4]. Inserting 2, 3 and 5 each costs exactly one comparison. The key is already larger than its left neighbour, so the inner loop stops at once. That is 3 comparisons and no shifts.

  2. Inserting 4: compare with 5. Since 4 < 5, shift 5 one place right (1 swap/shift). Then compare with 3. Since 4 > 3, stop. That is 2 comparisons and 1 shift.

  3. So , and IS performs exactly one swap/shift. Option (A) is false because , not 4. Option (C) is true.

  4. Bubble sort (BS), pass 1: compare (1,2), (2,3), (3,5), (5,4). Only the last pair swaps, giving [1, 2, 3, 4, 5]. That is 4 comparisons.

  5. Pass 2 makes 3 comparisons, (1,2), (2,3), (3,4), with no swap. With the early-exit (swapped flag) version BS stops here, so . Without early exit BS makes comparisons. Either way , so (B) is true. Note also that (A) fails on regardless of which BS version is used.

  6. Unnecessary comparisons: BS compares (1,2), (2,3) and (3,5) in pass 1, and these are already in order. IS compares 2 with 1, 3 with 2 and 5 with 3, which are also already in order. Only the comparison of 4 with 5 involves a misplaced pair. So both algorithms make at least one such comparison and (D) is true.

  7. Correct options: B, C, D.

KEY IDEA

Count comparisons directly. Insertion sort on an almost-sorted array costs one comparison per already-placed element plus the extra comparisons for the one displaced element. Bubble sort needs at least two passes here, because the early-exit pass that confirms sortedness is still a full pass of comparisons.

WATCH OUT FOR

Counting only the comparisons that lead to a swap, which gives N2 = 1 or 4. Also assuming IS needs only n - 1 = 4 comparisons. Inserting 4 needs two comparisons, so N2 = 5. Another slip is taking N1 = 4 by forgetting the second pass that confirms the array is sorted.

From the GATE 2026 DA paper. Every question of this paper · Download the full paper · All 18 Sorting & hashing questions, with notes

More Sorting & hashing questions