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 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 as argument, is __________. (Answer in integer)
ANSWER
The pseudocode runs bubble sort with the swap condition A[j] > A[j+1]. On a strictly descending array of 30 distinct integers, every single comparison performed is true, so every comparison also triggers a swap. Number of comparisons = number of swaps = 30×29/2 = 435.
Official answer: 435Source: Official answer key, GATE 2025 CS1 (IIT Roorkee)
The pseudocode is bubble sort with an ascending-sort swap rule: outer loop i = 0 to n-2, inner loop j = 0 to n-i-2, and whenever A[j] > A[j+1] the two are swapped.
Total number of comparisons made, from the loop bounds alone (independent of array contents):
Claim: for A[0..n-1] strictly descending, EVERY comparison the algorithm makes evaluates to true, so every comparison is also a swap. Proof sketch: within one outer pass over a strictly descending sub-array, at each inner step the value currently sitting in A[j] is the running maximum carried forward by the previous swaps in this pass, and A[j+1] is the next not-yet-touched original element — which is always strictly smaller than that running maximum. So A[j] > A[j+1] holds at every single comparison, in every pass.
Check on a small case, n = 4, A = [4,3,2,1]: pass i=0 compares (4,3), (4,2), (4,1) — all true, all swap, ending [3,2,1,4]; pass i=1 compares (3,2), (3,1) — all true, all swap, ending [2,1,3,4]; pass i=2 compares (2,1) — true, swap, ending [1,2,3,4]. All 4·3/2 = 6 comparisons were swaps, confirming the general argument.
Since every comparison is a swap, number of swaps = number of comparisons = n(n-1)/2. With n = 30: swaps = 30×29/2 = 435.
This matches the fact that bubble sort's swap count always equals the number of inversions in the input, and a strictly descending array of 30 distinct elements has the maximum possible number of inversions, .
KEY IDEA
This pseudocode is bubble sort with the comparison A[j] > A[j+1] triggering a swap — the standard scheme that sorts an array into ascending order. When the input is already sorted in the exact opposite (fully descending) order, this is the worst case for bubble sort: every comparison the algorithm ever makes finds a violation and swaps, so the swap count equals the comparison count, which equals the total number of inversions in the array, .
WATCH OUT FOR
Confusing "number of comparisons" with "number of swaps" when the array is NOT already sorted the way the algorithm wants: students correctly compute n(n-1)/2 comparisons but then assume swaps must be fewer (e.g. by miscounting how many passes actually trigger a swap), forgetting that a strictly descending input is exactly the worst case for this ascending-sorting bubble sort, where every comparison is also a swap.
From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 18 Sorting & hashing questions, with notes
