That Blue Square Thing

AQA Computer Science GCSE

September 2020: This page is the for the 2022 exam version of the AQA Computer Science GCSE course. This is for Year 10 teaching in September 2020.
These pages were copied over from the old syllabus and will get updated as I work through the new one. That means they won't always be totally up to date and I might miss something - check the updated date at the bottom of the page.

Algorithms - Sorting Algorithms

You need to know about two types of sorting algorithm:

The aim of a sort algorithm is to place items in a logical order (numerical or alphabetical generally)

It's important to be able to compare the pros and cons of each of the two algorithms.

PDF iconComparison of Bubble and Merge sorts - summary

Bubble Sort

A bubble sort works by working through an array comparing the items which are next to each other. It swaps any that are out of order and then repeats the process until no more swaps are made.

Here's an algorithm for a bubble sort on an array of numbers.

numbers <- [9, 5, 4, 15, 3, 8, 11, 2]
numItems <- LEN(numbers) -2 # why -2???
FOR i <- 0 TO numItems
FOR j <- 0 TO numItems - i
IF numbers[j] > numbers[j + 1] THEN # compare numbers
temp <- numbers[j] # a temporary store
numbers[j] <- numbers [j + 1] # swap j + 1 into j
numbers j + 1 <- temp # and put it back after it
ENDIF
ENDFOR
ENDFOR
OUTPUT numbers

It's quite a hard algorithm to read through and "get" the first time you do that. It helps if you work it through using a version of a trace table.

PDF iconBubble sort worked example - use this to get your head around how the algorithm works

PDF iconBubble sort example - a grid to work through

PDF iconBubble sort questions - and then try these questions. Think about the last one - it's not a straightforward question

Merge Sort

Merge sorting is more difficult to write as a clear algorithm because it relies upon repeating a process a number of times. This uses a very powerful (and advanced) programming technique called recursion - which you don't need to know about at all at GCSE.

The array is broken down by halving repeatedly until a set of single numbers are left. Pairs of these are then compared and sorted and the array built up again, layer by layer. Because each time a layer is combined the two parts have already been sorted, less passes are needed - and this makes the algorithm more efficient. Usually.

It's tricky to explain. Try using this worked example:

PDF iconMerge sort worked example - there is an exercise at the bottom for you to try as well.

PDF iconMerge sort example - a grid to work through