GATE CS 2025 Set 1 Q23 — Searching, Sorting, Hashing

The given pseudocode implements the standard Bubble Sort algorithm:

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]
}

For an array of size $n$, the outer loop runs for $i$ from $0$ to $n-2$. For each $i$, the inner loop runs for $j$ from $0$ to $n-i-2$.

Since the array $A$ of size $n = 30$ is initially sorted in descending order with distinct elements, every comparison A[j] > A[j+1] will evaluate to true. Thus, a swap operation is performed during every single comparison.

The total number of swaps is the sum of the number of inner loop iterations across all outer loop steps:

Substituting $n = 30$ into the formula:

Therefore, the number of swap operations performed is 435.