Skip to content

Question 36

What is the output of the following code?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
arr = [5, 2, 9, 1, 8]
n = len(arr)
for i in range(n):
    flag = False
    for j in range(0, n-i-1):
        if arr[j] > arr[j+1]:
            flag = True
            arr[j], arr[j+1] = arr[j+1], arr[j]
    if not flag:
        break

print(arr)
Hint

Trace the values in arr carefully as you run through the nested loop structure. Seeing that there is a flag variable inside the loop structure and how it is associated with a break statement, this code may encounter a premature exit from the loop.

There may also be a way to shortcut the tracing of this program, too.

Solution

This is an implementation similar to the bubble sort algorithm in action.

Given arr = [5, 2, 9, 1, 8] and n being the length of arr (i.e., n = 5), you could associate this first round of the outer loop as one round of bubbling the largest element to the end of the list.

i < n? flag j < (n-i-1)? arr[j] > arr[j+1]? arr break?
0 < 5 (True) False 0 < 4 (True) (arr[0] > arr[1])
5 > 2 (True)		 [2, 5, 9, 1, 8]
True 1 < 4 (True) (arr[1] > arr[2])
5 > 9 (False)
True 2 < 4 (True) (arr[2] > arr[3])
9 > 1 (True)		 [2, 5, 1, 9, 8]
True 3 < 4 (True) (arr[3] > arr[4])
9 > 8 (True)		 [2, 5, 1, 8, 9]
True 4 < 4 (False) No

From here, we can gather that the flag value changes to True as long as there is one swap within that iteration from the outer loop context point of view. Consequently, this means that if there are no swaps and flag remains False, this outer loop is broken immediately.

If we continue this behavior, we can observe the following:

End of i < n Iteration arr (Init: [5, 2, 9, 1, 8])
0 < 5 [2, 5, 1, 8, 9]
1 < 5 [2, 1, 5, 8, 9]
2 < 5 [1, 2, 5, 8, 9]
3 < 5 [1, 2, 5, 8, 9] (break here)

At the end, arr = [1, 2, 5, 8, 9].

Answer 
[1, 2, 5, 8, 9]