Sorting and searching algorithmsEdexcel International A Level Maths: Mind map

Exam questions on Sorting and searching algorithms

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.
   Find the total number of swaps needed to sort the list.2 marks
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.
   For the sub-list to the right of the first pivot, write down the next pivot and the sub-lists it creates.2 marks
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.
   Use the binary search to find $T=42$, stating the middle item chosen at each stage.3 marks