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)
Answer
435
Explanation
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