GATE DA 2026 | Question: 48

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)

Answer 1

Solution:

Given function:

\[
\texttt{fun(L, i=0)}
\]

In the loop, the function is called as

\[
\texttt{fun(data)}
\]

Since the second argument is not passed, the default value \( i=0 \) is used every time the function is called.

Thus, for each new call inside the loop, \( i \) is reinitialized to 0.

However, the list data  is modified in-place and retains its updated values.

 

The function compares adjacent elements and swaps them if they are out of order.

It then recursively proceeds to the next index.

 

Thus, one call to fun(data) performs exactly one left-to-right pass of Bubble Sort and returns the number of swaps in that pass.

Initial list:

\[
[5, 3, 4, 1, 2]
\]

The outer loop runs 5 times, so Bubble Sort performs 5 passes.

Pass 1 (i = 0):

\[
[5,3,4,1,2] \rightarrow [3,4,1,2,5]
\]

Swaps = 4

Pass 2 (i = 1):

\[
[3,4,1,2,5] \rightarrow [3,1,2,4,5]
\]

Swaps = 2

Pass 3 (i = 2):

\[
[3,1,2,4,5] \rightarrow [1,2,3,4,5]
\]

Swaps = 2

Pass 4 (i = 3):

Already sorted.

Swaps = 0

Pass 5 (i = 4):

Already sorted.

Swaps = 0

Total swaps:

\[
4 + 2 + 2 + 0 + 0 = 8
\]

Shortcut Method:

In Bubble Sort, the total number of swaps equals the number of inversions in the original array.

An inversion is a pair \( (i,j) \) such that \( i<j \) and \( L[i] > L[j] \).

For the array

\[
[5,3,4,1,2]
\]

The inversions are:

\[
(5,3), (5,4), (5,1), (5,2),
(3,1), (3,2),
(4,1), (4,2)
\]

Total inversions = 8.

Therefore, the output of the program is

\[
\boxed{8}
\]