Sorting and searching algorithmsEdexcel International A Level Maths: Revision notes

Section 1

Bubble sort

A bubble sort puts a list into order by repeated passes. In each pass, compare the first two items and swap them if they are in the wrong order, then compare the second and third, and so on to the end of the list. After pass 1 the largest item is at the end; after pass 2 the second largest is in place, so each pass can stop one place earlier. Stop when a whole pass makes no swaps. Example: 15, 8, 23, 4, 16, 9 becomes 8, 15, 4, 16, 9, 23 after pass 1 (4 swaps), 8, 4, 15, 9, 16, 23 after pass 2 (2 swaps), 4, 8, 9, 15, 16, 23 after pass 3 (2 swaps), and pass 4 makes no swaps.

Key termsbubble sortpassswap

Common mistake

Stopping when the list first looks sorted. The last pass, with no swaps, is needed to confirm it.

Section 2

The middle item

Quick sort and binary search both need the middle item. In a list of $N$ items the middle item is in position $\frac{N+1}{2}$ if $N$ is odd and $\frac{N+2}{2}$ if $N$ is even. So $N=9$ gives the 5th item, $N=6$ gives the 4th and $N=10$ gives the 6th. Apply this rule to each new sub-list, renumbering from 1.

Key termsmiddle item

Common mistake

Using position $\frac N2$ for an even list.

Section 3

Quick sort

Quick sort is a divide-and-conquer sort. Choose the middle item as the pivot. Write all items smaller than the pivot to its left and all larger items to its right, keeping their original order within each side. The pivot is now in its final position. Repeat on each sub-list (left first), choosing a new pivot each time, until every sub-list has at most one item. Example, 27, 14, 35, 8, 22, 41, 11, 19: pivot 22 gives 14, 8, 11, 19 | 22 | 27, 35, 41. Then pivots 11 and 35 give 8 | 11 | 14, 19 and 27 | 35 | 41. Finally pivot 19 gives 14 | 19. The sorted list is 8, 11, 14, 19, 22, 27, 35, 41.

Key termsquick sortpivotsub-list

Exam tip

Show each pivot (underline or write it) and both sub-lists so the method is clear.

Section 4

Binary search

A binary search finds an item in a list that is already in order. Find the middle item. If it equals the target $T$ , stop. If $T$ is smaller, discard the middle item and everything after it; otherwise discard it and everything before it. Repeat on what remains. If no items remain, $T$ is not in the list. Example: list 3, 8, 12, 17, 21, 25, 29, 34, 38, 42, 47, 53, 60 and $T=42$ . The middles are 29, 47, 38 and 42, so 42 is found. For $T=20$ the middles are 29, 17, 25 and 21, then nothing remains, so 20 is not present.

Key termsbinary search

Common mistake

Applying a binary search to a list that is not in order. The method only works for an ordered list.

Section 5

Choosing and describing methods

Bubble sort is simple but may need many passes. Quick sort usually needs far fewer comparisons for long lists. A binary search needs at most about $\log_2 N$ comparisons, where a list of $N$ items is halved each time, much fewer than checking every item in turn. Always show each pass or sub-list clearly, give the final result and state any conclusion (found or not found) in words.

That's the notes covered.

Carry on to the next subtopic.

Exam questions on Sorting and searching algorithms

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

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).