“””
QUESTION 4: Stacks
4 marks, ~10 minutes
Here’s a mystery_sort function that is meant to sort some kind of list, i.e.,
lists that satisfy certain preconditions.
Read the code and answer the questions below.
“””
def mystery_sort(lst: List[int]) -> List[int]:
s1 = Stack()
s2 = Stack()
flag = True
i = 0
while i < len(lst):
if flag and (s1.is_empty() or lst[i] > s1.peek()):
s1.push(lst[i])
else:
flag = False
s2.push(lst[i])
i += 1
res = []
while not s2.is_empty():
res.append(s2.pop())
while not s1.is_empty():
s2.push(s1.pop())
while not s2.is_empty():
res.append(s2.pop())
return res
“””
(a) Below, provide an example input such that mystery_sort return a sorted
copy of the list in non-decreasing order.
Requirements:
– the input list must be of size 7
– the input must NOT be sorted in either non-increasing or non-decreasing order.
TODO:
Write your input here:
(b) Below, provide an example input that is sorted in non-decreasing order
but the return value of mystery_sort is NOT sorted.
Requirement:
– the input list must be of size 5
TODO:
Write your input here:
(c) Describe a precondition for the input list such that the mystery_sort()
method returns a sorted copy of the input in non-decreasing order.
Your precondition should include as many valid inputs as possible.
TODO:
Write your precondition here:
(d) What is the time complexity of mystery_sort in terms of n, the size of the
input list? Assume that the Stack is implemented in the efficient way that we
learned in this course.
TODO:
Write your answer in big-Oh (O(???)) and briefly justify.
“””