They say a picture is worth a thousand words, and that is probably true, IF you are ready to understand the picture! When this is the case, we often experience those wonderful aha moments where understanding happens almost instantaneously, as if someone has switched on a light in our mind. However, there is usually a lot that needs to happen for these moments to occur.
So how does this relate to learning Bubble Sort Computer Science for GCSE and A Level? Well, the point is that understanding often takes time to develop. It can appear to happen suddenly, but usually there is a lot of “root growth” that needs to happen first.
What I have written here is generally applicable to learning ANY difficult concept in Computer Science, but in order to provide focus I will address a particular topic: bubble sort. The bubble sort algorithm is famous among computer science students both at GCSE and A Level. Although it is not a great algorithm in terms of efficiency (for those who know about these things, bubble sort has a worst-case and average complexity of О(n²)), it does have the merit of being quite intuitive and reasonably easy to understand with a little effort from students.
There are actually two levels of understanding that might be required for this algorithm:
- understanding the algorithm for GCSE-style questions about the state of a list of elements after a certain number of passes
- understanding the how to implement the algorithm in a programming language
Here we will focus on understanding the algorithm without considering implementation. For students who do want to address the coding aspect, I have provided a Python implementation later on. It is important to note that it will be very difficult to write the code for this algorithm unless you understand if fully first, away from a computer screen,
How to learn Bubble Sort for Computer Science GCSE and A Level
Here is a possible order of events for effectively learning how the bubble sort algorithm works and being able to answer GCSE exam questions on it:
- Watch this animation. Slow it down, speed it up, get a feel for the high-level flow of the algorithm
- Read or listen to an explanation of how it works
- Follow along with physical objects like cards if possible. Do this for several examples.
- On paper, or better still a whiteboard (mini whiteboards are very useful for students at any level). work through some more examples
- Watch the animation again, this time paying attention to all the details
- Let understanding happen. If it doesn’t, go back to
- Do lots of practice questions
An example of the Bubble Sort Algorithm
Sort the list of numbers 66 21 38 15 89 49 using bubble sort.
- 66 21 38 15 89 49 Compare 66 and 21, swap them
- 21 66 38 15 89 49 Compare 66 and 38, swap them
- 21 38 66 15 89 49 Compare 66 and 15, swap them
- 21 38 15 66 89 49 Compare 66 and 89, don’t swap
- 21 38 15 66 89 49 Compare 89 and 49, swap them
21 38 15 66 49 90 End of first pass
End of second pass: 21 15 38 49 66 89
End of third pass: 15 21 38 49 66 89
In the fourth pass, no swaps occur so we can be certain that the list is sorted. (Think about why if this is not immediately obvious.)
It is worth noting that in the exam you may be expected to give the state of the list after a whole pass, or after a certain number of swaps within a single pass and you should check to make sure you are answering the exact question you have been asked.
In terms of pictures-vs-words, if we take “words” to mean all the thinking, trying, scribbling etc. that goes into getting our heads around an algorithm, then it seems likely that some kind of loop involving picture – words – picture etc. may be the best way to reach true understanding.
Bubble Sort in Python for Computer Science GCSE and A Level
Here is a python implementation of Bubble Sort which you may find helpful. The process for fully grokking the actual code for algorithms involves some other steps which we will look at in a future article. Much of what I’ve written above will still apply there too.
"""Bubble Sort Algorithm""" values = [66, 21, 38, 15, 89, 49] def bubble_sort(arr): """ Returns a list sorted in ascending order. We are assuming an integer list as input """ for passnum in range(len(arr) - 1): for i in range(len(arr) - 1 - passnum): if arr[i] > arr[i + 1]: temp = arr[i + 1] arr[i + 1] = arr[i] arr[i] = temp print( "After Pass " + str(passnum + 1) + ", inner loop " + str(i + 1) + ":", arr, ) return arr print(bubble_sort(values))
The Python implementation of the bubble sort algorithm above does not allow for early exit once a complete pass is made with no swaps, so its efficiency can be improved. Why not have a go at making that change for yourself, and post your solution in the comments?