GATE DA 2024 | Question 45

MCQ · 2 marks · −0.66

Consider the following sorting algorithms:

(i) Bubble sort
(ii) Insertion sort
(iii) Selection sort

Which ONE among the following choices of sorting algorithms sorts the numbers in the array [4, 3, 2, 1, 5] in increasing order after exactly two passes over the array?

  1. Option A: (i) only
  2. Option B: (iii) only (correct)
  3. Option C: (i) and (iii) only
  4. Option D: (ii) and (iii) only

Answer

(B)

Explanation

Trace two passes of each algorithm on [4, 3, 2, 1, 5]:

  • Bubble sort: pass 1 carries 4 to its place, giving [3, 2, 1, 4, 5]; pass 2 carries 3, giving [2, 1, 3, 4, 5]. Not yet sorted.
  • Insertion sort: pass 1 inserts 3, giving [3, 4, 2, 1, 5]; pass 2 inserts 2, giving [2, 3, 4, 1, 5]. Not yet sorted.
  • Selection sort: pass 1 swaps the minimum 1 into the first position, giving [1, 3, 2, 4, 5]; pass 2 swaps 2 into the second position, giving [1, 2, 3, 4, 5]. Sorted.

Only selection sort is done, because its two swaps happen to fix every misplaced element; bubble sort and insertion sort each need a third pass.

Answer: B