GATE CS Searching and Sorting Previous Year Questions

GATE CS 2025 Set 1 | Question 33

NAT · 1 mark

The pseudocode of a function fun() is given below:

fun(int A[0,…,n-1]){
    for i=0 to n-2
        for j=0 to n-i-2
            if (A[j]>A[j+1])
                then swap A[j] and A[j+1]

}

Let \(A[0, \ldots, 29]\) be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function fun() is called with \(A[0, \ldots, 29]\) as argument, is __________. (Answer in integer)

Your answer

Explanation

Answer: 435

fun() is bubble sort. Each swap exchanges one adjacent out-of-order pair, so it removes exactly one inversion, and the total number of swaps equals the number of inversions in the input.

In a descending array of 30 distinct values every pair is an inversion, so the count is \(\binom{30}{2} = \frac{30 \times 29}{2} = 435\). Pass by pass gives the same total: pass \(i\) makes \(29 - i\) comparisons and every one of them swaps, so \(29 + 28 + \cdots + 1 = 435\).

Answer: 435

GATE CS 2025 Set 2 | Question 20

MCQ · 1 mark · −0.33

Consider an unordered list of \(N\) distinct integers.

What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

1 \(N - 1\) \(N\) \(2N - 1\)

Explanation

Answer: (A)

Pick any two elements and compare them once. Because the integers are distinct, one of them is strictly smaller, and that smaller element cannot be the largest in the list: the other element beats it. So one comparison always suffices.

Zero comparisons cannot work, since without any comparison every element we might pick could still be the maximum. Hence the minimum is 1.

\(N - 1\) comparisons are what it takes to find the largest element itself, which is a different task; the question only asks for some element that is not the largest.

Answer: A

GATE CS 2025 Set 2 | Question 41

MCQ · 2 marks · −0.66

An array \(A\) of length \(n\) with distinct elements is said to be bitonic if there is an index \(1 \le i \le n\) such that \(A[1..i]\) is sorted in the non-decreasing order and \(A[i+1..n]\) is sorted in the non-increasing order.

Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons by an algorithm that searches for an element in a bitonic array \(A\)?

\(\Theta(n)\) \(\Theta(1)\) \(\Theta(\log^{2} n)\) \(\Theta(\log n)\)

Explanation

Answer: (D)

Search in three binary-search phases:

Find the peak: compare \(A[m]\) with \(A[m+1]\). If \(A[m] < A[m+1]\) the peak is to the right, otherwise at \(m\) or to its left. Each comparison halves the range: \(O(\log n)\).
Binary search the increasing part \(A[1..i]\).
Binary search the decreasing part \(A[i+1..n]\).

That is \(O(\log n)\) comparisons in all, and no algorithm can do better: a sorted array is itself bitonic (take \(i = n\)), and searching a sorted array needs \(\Omega(\log n)\) comparisons. So the bound is \(\Theta(\log n)\); \(\Theta(\log^{2} n)\) is achievable but not the best, and \(\Theta(1)\) is impossible.

Answer: D