That Blue Square Thing

AQA Computer Science GCSE

February 2019: this area of the site is being built just now. There are areas where there is no content yet. That will get added over the next 6 months or so.

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.

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