Sorting and searching algorithmsEdexcel International A Level Maths: Subtopic test

1. 1
   The 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

   (b)

   How many passes are needed in total, including the final pass that makes no swaps?

   [1 mark]

   • A$3$
   • B$4$
   • C$5$
   • D$6$

   (c)

   Find the total number of swaps needed to sort the list.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   The 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 $N$ items, its middle item is in position $\frac{N+1}{2}$ when $N$ is odd and $\frac{N+2}{2}$ when $N$ 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$28$
   • B$31$
   • C$24$
   • D$19$

   (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

   (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]

   Total for question 2: 4 marks

3. 3
   The 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 $T$. The middle item of a list of $N$ items is in position $\frac{N+1}{2}$ if $N$ is odd and $\frac{N+2}{2}$ if $N$ is even. If $T$ 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 $T$ is found or no items remain.

   (a)

   Use the binary search to find $T=42$, stating the middle item chosen at each stage.

   [3 marks]

   (b)

   Use the binary search to show that $T=20$ is not in the list.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   The 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 $N$ items, its middle item is in position $\frac{N+1}{2}$ when $N$ is odd and $\frac{N+2}{2}$ when $N$ is even. Show the pivot and the sub-lists at each stage.

   [6 marks]

   (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.
   (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.

   [6 marks]

   Total for question 4: 12 marks

End of questions