The pseudocode of a function $fun()$ is given below: \(\begin{aligned}&\text{fun(int A[0, ... , n-1])} \…

Question

The pseudocode of a function $fun()$ is given below: $\begin{aligned}&\text{fun(int A[0, ... , n-1])} \ &\text{\{} \ &\quad \text{for } i = 0 \text{ to } n-2 \ &\quad \quad \text{for } j = 0 \text{ to } n-i-2 \ &\quad \quad \quad \text{if } (A[j] > A[j+1]) \ &\quad \quad \quad \quad \text{then swap A[j] and A[j+1]} \ &\text{\}}\end{aligned}$ Let $𝐴[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 $𝐴[0, … ,29]$ as argument, is __________. (Answer in integer)

Accepted Answer

Correct answer: 435 — Answer: 435 Explanation: The given code is the standard bubble sort that swaps adjacent out-of-order elements. The total number of swaps performed equals the initial number of inversions in the array. For 30 distinct integers in descending order, every pair of indices (i, j) with i < j is an inversion. Number of such pairs (inversions) = 30 choose 2 = 30 * 29 / 2 = 435 Each adjacent swap reduces the inversion count by exactly 1, so the total number of swaps equals the initial inversion count, which is 435.

The pseudocode of a function \(fun()\) is given below:…