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

The pseudocode provided is an implementation of Bubble Sort. Let’s analyze the number of swap operations in the case where the array is initially sorted in descending order: The outer loop runs from \( i = 0 \) to \( n-2 \), where \( n = 30 \). Therefore, the outer loop runs \( 29 \) times.
The inner loop runs from \( j = 0 \) to \( n-i-2 \), which means the number of iterations decreases as \( i \) increases.
For each value of \( i \), the number of comparisons in the inner loop is: \[ n - i - 2 \] Thus, the total number of comparisons (and therefore the number of potential swaps) is the sum of the number of comparisons for each value of \( i \) from 0 to \( n-2 \). Step 1: Total Number of Comparisons
The number of comparisons for each value of \( i \) is:
For \( i = 0 \), the inner loop runs \( n-1 \) times.
For \( i = 1 \), the inner loop runs \( n-2 \) times.
For \( i = 2 \), the inner loop runs \( n-3 \) times.
...
For \( i = n-2 \), the inner loop runs 1 time.
Thus, the total number of comparisons is the sum of the first \( n-1 \) integers: \[ {Total comparisons} = (n-1) + (n-2) + \ldots + 1 = \frac{n(n-1)}{2} \] For \( n = 30 \): \[ {Total comparisons} = \frac{30 \times 29}{2} = 435 \] Step 2: Number of Swaps
In a Bubble Sort, a swap occurs every time a comparison finds that \( A[j]>A[j+1] \). Since the array is initially sorted in descending order, every comparison will result in a swap. Thus, the number of swaps is equal to the total number of comparisons, which is 435. Therefore, the number of swap operations performed is 435.