Question

Consider the given Python program.

def fun(L, i=0):
    if i >= len(L)-1:
        return 0
    if L[i] > L[i+1]:
        L[i+1], L[i] = L[i], L[i+1]
        return 1+fun(L, i+1)
    else:
        return fun(L, i+1)

data = [5, 3, 4, 1, 2]
count = 0
for _ in range(len(data)):
    count += fun(data)
print(count)

The output of the program is _______. (Answer in integer)

Hint:

Each call to fun performs one bubble-sort pass and counts its swaps; running it 5 times over a 5-element list is enough to fully sort it, so the total equals the number of inversions in the original list.

Answer 1

Correct Answer: 8

Instead of simulating every pass step by step, use a shortcut: each call to fun does one left-to-right bubble pass, and every time it swaps two adjacent elements, it fixes exactly one "inversion" (a pair of positions where the earlier element is bigger than a later element). Running enough passes to fully sort a 5-element list means every inversion gets fixed exactly once across all the passes, so the total count printed at the end equals the number of inversions present in the original array.

First count the inversions in the starting array $[5, 3, 4, 1, 2]$. An inversion is any pair of positions $(i, j)$ with $i < j$ where the value at $i$ is bigger than the value at $j$. Check every pair:

1. (5, 3): $5 > 3$, inversion.
2. (5, 4): $5 > 4$, inversion.
3. (5, 1): $5 > 1$, inversion.
4. (5, 2): $5 > 2$, inversion.
5. (3, 4): $3 < 4$, not an inversion.
6. (3, 1): $3 > 1$, inversion.
7. (3, 2): $3 > 2$, inversion.
8. (4, 1): $4 > 1$, inversion.
9. (4, 2): $4 > 2$, inversion.
10. (1, 2): $1 < 2$, not an inversion.

That gives 8 inversions out of the 10 possible pairs.

Now check that 5 passes is really enough to clear all of them. A single left-to-right bubble pass is guaranteed to move the largest remaining unsorted element all the way to its correct position at the far right. With 5 elements, at most 4 passes are ever needed to fully sort the list, and the loop here runs 5 passes, one more than needed. So by the time all 5 calls to fun finish, the list is completely sorted and every one of the 8 original inversions has been resolved by exactly one adjacent swap.

Since each swap adds exactly 1 to count and there are 8 swaps in total across the 5 passes, count ends at 8, and that is what print(count) outputs.

$$\boxed{8}$$