GATE 2024 DA Q.45: solution and answer

Official answer: BSource: Official answer key, GATE 2024 DA (IISc Bengaluru)

1. Trace each algorithm on $[4,3,2,1,5]$ and look at the array after exactly two passes. A pass of bubble sort is one left-to-right sweep of adjacent compares. A pass of insertion sort inserts the next element into the sorted prefix. A pass of selection sort puts the minimum of the unsorted part into its final place.

2. Bubble sort, pass 1: compare $(4,3)$ and swap, giving $[3,4,2,1,5]$. Compare $(4,2)$ and swap, giving $[3,2,4,1,5]$. Compare $(4,1)$ and swap, giving $[3,2,1,4,5]$. Compare $(4,5)$ and leave it. The array is $[3,2,1,4,5]$.

3. Bubble sort, pass 2: compare $(3,2)$ and swap, giving $[2,3,1,4,5]$. Compare $(3,1)$ and swap, giving $[2,1,3,4,5]$. Compare $(3,4)$ and $(4,5)$ and leave both. The array is $[2,1,3,4,5]$. The first two entries are still out of order, so bubble sort is not finished.

4. Insertion sort, pass 1: insert $3$ into the sorted prefix $[4]$, giving $[3,4,2,1,5]$.

5. Insertion sort, pass 2: insert $2$ into $[3,4]$, giving $[2,3,4,1,5]$. The element $1$ has not yet been inserted, so the array is not sorted.

6. Selection sort, pass 1: the minimum of the whole array is $1$. Swap it with the first position, giving $[1,3,2,4,5]$.

7. Selection sort, pass 2: the minimum of the remaining part $[3,2,4,5]$ is $2$. Swap it with the second position, giving $[1,2,3,4,5]$. The array is sorted.

8. Only selection sort has the array fully sorted after exactly two passes, so the answer is (iii) only, which is option (B).