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

Step 1: Understand what fun does in one call.
The function fun(L, i) walks through the list L starting at index i. At each position it compares L[i] with L[i+1]. If L[i] is bigger, it swaps the two elements and adds 1 to the count, then moves on to i+1. If not, it just moves on to i+1 without adding anything. It stops when i reaches the last valid index.
This is exactly one left-to-right pass of bubble sort: it walks the whole list once, and counts how many swaps happened during that single pass.

Step 2: Note the outer loop.
data = [5, 3, 4, 1, 2] has 5 elements, so range(len(data)) runs 5 times. Each iteration calls fun(data) once (i defaults back to 0 each time) and adds its return value to count. So the program runs 5 full bubble-sort passes over data and adds up the total number of swaps across all 5 passes.

Step 3: Trace Pass 1.
Start: [5, 3, 4, 1, 2]
i=0: 5 > 3, swap -> [3, 5, 4, 1, 2], swaps so far = 1
i=1: 5 > 4, swap -> [3, 4, 5, 1, 2], swaps so far = 2
i=2: 5 > 1, swap -> [3, 4, 1, 5, 2], swaps so far = 3
i=3: 5 > 2, swap -> [3, 4, 1, 2, 5], swaps so far = 4
Pass 1 total swaps = 4. count = 4. List is now [3, 4, 1, 2, 5].

Step 4: Trace Pass 2.
Start: [3, 4, 1, 2, 5]
i=0: 3 > 4? No, no swap.
i=1: 4 > 1, swap -> [3, 1, 4, 2, 5], swaps so far = 1
i=2: 4 > 2, swap -> [3, 1, 2, 4, 5], swaps so far = 2
i=3: 4 > 5? No, no swap.
Pass 2 total swaps = 2. count = 4 + 2 = 6. List is now [3, 1, 2, 4, 5].

Step 5: Trace Pass 3.
Start: [3, 1, 2, 4, 5]
i=0: 3 > 1, swap -> [1, 3, 2, 4, 5], swaps so far = 1
i=1: 3 > 2, swap -> [1, 2, 3, 4, 5], swaps so far = 2
i=2: 3 > 4? No. i=3: 4 > 5? No.
Pass 3 total swaps = 2. count = 6 + 2 = 8. List is now [1, 2, 3, 4, 5], fully sorted.

Step 6: Passes 4 and 5.
The list [1, 2, 3, 4, 5] is already sorted, so every comparison in pass 4 and pass 5 finds L[i] <= L[i+1] and no swap happens. Both passes add 0 to count. count stays at 8 after all 5 iterations.

Final Answer:
print(count) outputs 8. \[ \boxed{8} \]