Skip to content

Question 35

What is the output of the following code?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
lst = [9,12,3,7,11,2,4,8,5]
left = 1
right = len(lst)-1
while left < right:
    while lst[left] < lst[0]:
        left += 1
    while lst[right] > lst[0]:
        right -= 1
    if left < right:
        lst[left],lst[right] = lst[right],lst[left]

print(lst)
Hint

Trace the values in lst as well as that of left and right carefully as you run through the loop structure.

Solution

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

Given lst = [9, 12, 3, 7, 11, 2, 4, 8, 5], len(lst) = 9.

  • left = 1
  • right = len(lst) - 1 = 9 - 1 = 8
left < right? left lst[left] < lst[0]? right lst[right] > lst[0]? left < right? lst
1 < 8 (True) 1 12 < 9 (False) 8 5 > 9 (False) 1 < 8 (True) [9, 5, 3, 7, 11, 2, 4, 8, 12]
1 < 8 (True) 1 5 < 9 (True)
2 3 < 9 (True)
3 7 < 9 (True)
4 11 < 9 (False) 8 12 > 9 (True)
4 7 8 > 9 (False) 4 < 7 (True) [9, 5, 3, 7, 8, 2, 4, 11, 12]
4 < 7 (True) 4 8 < 9 (True)
5 2 < 9 (True)
6 4 < 9 (True)
7 11 < 9 (False) 7 11 > 9 (True)
7 6 4 > 9 (False) 7 < 6 (False)
7 < 6 (False) [9, 5, 3, 7, 8, 2, 4, 11, 12]
Answer 
[9, 5, 3, 7, 8, 2, 4, 11, 12]