Question

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).

Hint:

In Bubble Sort, the number of swaps is equal to the number of comparisons when the array is initially sorted in descending order, as every comparison leads to a swap.

Answer 1

Correct Answer: 435

Problem Analysis:

For an array sorted in descending order, every adjacent pair $(A[j], A[j+1])$ will satisfy the condition $A[j] > A[j+1]$. In Bubble Sort, this triggers a swap for every single comparison made until the array reaches its sorted state.

---

Step 1: Identify the Arithmetic Progression of Swaps

In the first pass ($i=0$), the largest element is at the start and must bubble down to the end, requiring $(n-1)$ swaps. In the second pass ($i=1$), the next largest element requires $(n-2)$ swaps to reach its correct position. This continues until the final pass requires only $1$ swap.

The total number of swaps is the sum: $S = \sum_{k=1}^{n-1} k$

---

Step 2: Apply the Summation Formula

The sum of the first $k$ integers is given by the formula:$$S = \frac{k(k+1)}{2}$$In our case, $k = n-1$. Substituting $n = 30$:$$k = 30 - 1 = 29$$

---

Step 3: Calculate the Final Value

Plugging $29$ into our summation formula:$$S = \frac{29 \times (29 + 1)}{2}$$$$S = \frac{29 \times 30}{2}$$$$S = 29 \times 15 = \mathbf{435}$$

---

Final Answer:

The total number of swap operations performed is: 435