Skip to content

Question 23

Consider the following code that calls the modified magic function from the tutorial (qSort):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def magic(lst):
    if not lst:
        return lst
    print('Abracadabra!')
    pivot = lst[0]
    lsta = magic([i for i in lst if i < pivot])
    lstb = magic([i for i in lst if i > pivot])
    return lsta + [pivot] + lstb

magic([22, 6, 18, 39, 1])

How many times will 'Abracadabra!' be printed?

Hint

Given the value lst = [22, 6, 18, 39, 1] as per how magic() is called, run through the function and then determine the final output of lsta + [pivot] + lstb.

Solution

Given inner variable lst = [22, 6, 18, 39, 1] as per calling magic([22, 6, 18, 39, 1]),

  • if not lst: False, since lst is not empty. Skip if block
  • 'Abracadabra!' printed
  • pivot = lst[0] = 22
  • lsta returns output of magic() with list of elements in lst smaller than pivot
    • magic([6, 18, 1]) \(\Rightarrow\) 'Abracadabra!' printed;
      • magic([1]) \(\Rightarrow\) 'Abracadabra!' printed;
        • magic([]) - return []
      • Hence, magic([1]) returns [] + [1] + [] = [1]
      • magic([18]) \(\Rightarrow\) 'Abracadabra!' printed;
        • magic([]) - return []
      • Hence, magic([18]) returns [] + [18] + [] = [18]
    • Hence, magic([6, 18, 1]) returns [1] + [6] + [8] = [1, 6, 18]
  • lstb returns output of magic() with list of elements in lst larger than pivot
    • magic([39]) \(\Rightarrow\) 'Abracadabra!' printed;
      • magic([]) - return []
    • Hence, magic([39]) returns [] + [39] + [] = [39]

Hence, magic([22, 6, 18, 39, 1]) returns [1, 6, 18] + [22] + [39] = [1, 6, 18, 22, 39]

Notice that 'Abracadabra!' is printed each time magic() is called. Right here, it can be inferred that magic() is recursively called a total of 4 times in addition to the 1 initial call, which is representative of the number of elements inside lst.

Answer

5