The GATE Grind

GATE 2025 CS (CS1) – Question 33

Algorithms · Searching, Sorting and Hashing · 1 mark · Numerical answer

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,...,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,...,29]$ as argument, is __________. (Answer in integer)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 435

Explanation

This is bubble sort. The inner loop compares adjacent elements and swaps them if the left one is larger.

For an array in **descending** order every comparison finds a larger element on the left, so **every comparison causes a swap**.

Number of comparisons $=\sum_{i=0}^{n-2}(n-i-1)=\frac{n(n-1)}{2}$. With $n=30$:
$$\frac{30\cdot29}{2}=\mathbf{435}\text{ swaps}.$$

More Searching, Sorting and Hashing questions

All Searching, Sorting and Hashing questions →