AQA Computer Science GCSE
Algorithms - Sorting Algorithms
You need to know about two types of sorting algorithm:
- bubble sort
- merge sort
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.
Comparison 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.
numItems <- LEN(numbers) -2 # why -2???
FOR i <- 0 TO numItems
numbers[j] <- numbers [j + 1] # swap j + 1 into j
numbers j + 1 <- temp # and put it back after it
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.
Bubble sort worked example - use this to get your head around how the algorithm works
Bubble sort example - a grid to work through
Bubble 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:
Merge sort worked example - there is an exercise at the bottom for you to try as well.
Merge sort example - a grid to work through