GATE 2025 CS (CS1) – Question 33
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}.$$