Python 3

Question 2 (8 marks) This question is about sorting algorithms (a) (3 marks) What happens in insertion sort when you are given a sorted list of numbers? Explain your answer (b) (4 marks) Show how the following list would be sorted by selection sort [20, 67, 2, 8, -2, 6, 0, 35, 4,18] Show each iteration as a separate line and make clear what has changed (c) (1 mark) State the invariant for selection sort Question 3 (5 marks) This question is about recursive strategies to problems. Consider the task of performing division by successive subtraction. In this case, n be considered equivalent to subtracting N from X until X is less than N. Whatever X becomes after this process is the remainder and the number of subtractions performed is the quotient. For example given X- 27 and N = 4, X would become 23 then 19, 15, 11, 7 and finally 3. This makes the remainder 3 and the quotient 6 as there were six subtractions required to make X