Edexcel International A Level Maths
Sorting and searching algorithms
Total 27 marks
Name
Class
Date
- 1The list 15, 8, 23, 4, 16, 9 is to be sorted into ascending order using a bubble sort. In each pass, adjacent items are compared from the left and swapped if they are in the wrong order.(a)What is the list after the first pass?[1 mark]
- A8, 15, 23, 4, 16, 9
- B4, 8, 9, 15, 16, 23
- C8, 15, 4, 16, 9, 23
- D8, 4, 15, 9, 16, 23
Show the mark scheme
Mark scheme
Answer: C(b)How many passes are needed in total, including the final pass that makes no swaps?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: B(c)Find the total number of swaps needed to sort the list.[2 marks]Show the mark scheme
Mark scheme
M1: swaps per pass (and in the last pass), at least three correct
A1:Total for question 1: 4 marks
- 2The list 31, 12, 45, 7, 28, 19, 52, 3, 36, 24 is to be sorted into ascending order using quick sort. The pivot is always the middle item of the list being sorted. If a list has items, its middle item is in position when is odd and when is even. In each pass, items smaller than the pivot are written to its left and items larger than the pivot to its right, keeping their original order.(a)Which item is the first pivot?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: D(b)After the first pass, which items are to the right of the pivot?[1 mark]- A31, 45, 28, 52, 36, 24
- B24, 28, 31, 36, 45, 52
- C24, 36, 52, 28, 45, 31
- D52, 45, 36, 31, 28, 24
Show the mark scheme
Mark scheme
Answer: A(c)For the sub-list to the right of the first pivot, write down the next pivot and the sub-lists it creates.[2 marks]Show the mark scheme
Mark scheme
B1: pivot (4th item of the 6 items)
B1: left sub-list and an empty right sub-listTotal for question 2: 4 marks
- 3The numbers 3, 8, 12, 17, 21, 25, 29, 34, 38, 42, 47, 53, 60 are in ascending order and are to be searched using a binary search for a number . The middle item of a list of items is in position if is odd and if is even. If is smaller than the middle item, the middle item and all items after it are discarded. Otherwise the middle item and all items before it are discarded. The search stops when is found or no items remain.(a)Use the binary search to find , stating the middle item chosen at each stage.[3 marks]
Show the mark scheme
Mark scheme
B1: first middle item (7th of 13)
M1: second middle item (4th of the 6 items )
A1: third middle item , then found(b)Use the binary search to show that is not in the list.[4 marks]Show the mark scheme
Mark scheme
M1: first middle item , leaving
M1: second middle item (4th of 6), leaving
A1: third middle item , leaving , then middle item
A1: no items remain, so is not in the listTotal for question 3: 7 marks
- 4The list 27, 14, 35, 8, 22, 41, 11, 19 is to be sorted into ascending order.(a)Use quick sort, with the middle item as the pivot, to sort the list. If a list has items, its middle item is in position when is odd and when is even. Show the pivot and the sub-lists at each stage.[6 marks]
Show the mark scheme
Mark scheme
B1: first pivot (5th of 8)
M1: sub-lists and
M1: pivots (3rd of 4) and (2nd of 3)
A1: sub-lists and ; and
B1: pivot for the list , giving on the left
A1: sorted list(b)The list is instead sorted using a bubble sort. In each pass, adjacent items are compared from the left and swapped if they are in the wrong order.[6 marks]
(i) Write down the list after the first pass.
(ii) Write down the list after the second pass.
(iii) The list is in order after the fifth pass. Explain why a sixth pass is still needed.Show the mark scheme
Mark scheme
M1: (i) first four items correct
A1: (i)
M1: (ii) second pass applied to their list from (i)
A1: (ii)
B1: (iii) the sixth pass makes no swaps
B1: (iii) only a pass with no swaps shows that the list is sortedTotal for question 4: 12 marks
End of questions