GATE 2024 DA – Question 45
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?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) (iii) only
Explanation
Bubble sort: after pass 1 the array is $[3, 2, 1, 4, 5]$ and after pass 2 it is $[2, 1, 3, 4, 5]$, not sorted. Insertion sort: after two passes (inserting the 2nd and 3rd elements) it is $[2, 3, 4, 1, 5]$, not sorted. Selection sort: pass 1 swaps 1 into the first place giving $[1, 3, 2, 4, 5]$, and pass 2 swaps 2 into the second place giving $[1, 2, 3, 4, 5]$, which is sorted. So only selection sort works.