- [Craig] In this video, we're going to be looking at the bubble sort algorithm.
(uplifting piano jingle)
So, before we work through an example of the bubble sort algorithm,
let's first summarise its key features.
It sorts an unordered list of items.
It compares each item with the next one and then swaps them if they're out of order.
The algorithm finishes when no more swaps need to be made.
In effect, it bubbles up the largest or smallest item to the end of the list in successive passes.
This is the most inefficient of the sorting algorithms but it's very easy to implement.
This makes it a popular choice for very small data sets.
So, here's a data set of breakfast cereals.
The original data to sort is shown on the left,
and the sorted data that we're trying to achieve is shown in green on the right.
And the object is to put them in alphabetical order with the lowest one at the bottom,
so Cornflakes, Crunchy Nut Clusters, Fruit 'n' Fibre, Sugar Puffs and Weetabix at the top.
We're now going to go through the steps of the algorithm to see how we can get to the sorted data set.
So, we start by comparing the first two items of the list.
Are they in the right order?
Well, they're not in the right order, so we swap them over.
We now compare the next two items in our list, so that's Weetabix and Sugar Puffs.
Are they in the right order?
Well, yes they are, so we leave them exactly where they are.
We now compare the next two items in our list, Fruit 'n' Fibre and Weetabix.
Are they in the right order?
Well, they're not in the right order, so we swap them over.
And finally, we compare the last two items in our list, Cornflakes and Weetabix.
Are they in the right order?
Well, no they're not, so we swap them over.
Now we've completed what we call our first pass.
Now what we can be sure of is that Weetabix is now in the correct place.
In effect, it's bubbled up to the top of the list.
We now have to perform a second pass.
So, Weetabix is in the correct place, so we can ignore that.
but we repeat the algorithm, starting with comparing Sugar Puffs and Crunchy Nut Clusters
because they're the first two items of the list,
and we ask, are they in the right order?
They are, so we leave them where they are.
We compare the next two items on our list.
Are they in the right order?
Well, they're not, so we swap them over.
We compare the next two items in our list.
Are they in the right order?
And they're not, so we swap them over.
We've now completed our second pass,
and we can be sure that Weetabix and Sugar Puffs, which has just bubbled up to the top, are in the correct place.
So, we now have to do a third pass.
So, compare the first two items of the list, that's Fruit 'n' Fibre and Crunchy Nut Clusters.
Are they in the right order?
Well, they are in the right order, so we leave them where they are.
We now compare the next two items, Cornflakes and Fruit 'n' Fibre.
Are they in the right order?
They are not in the right order, so we swap them over.
We've now completed our third pass,
and we can be sure that Weetabix, Sugar Puffs and Fruit 'n' Fibre are all in the correct place.
We simply repeat our algorithm on the unsorted part of the list.
Well, the unsorted part of the list is only the first two items,
so we compare them just like before, and we ask, are they in the right order?
They're not in the right order, so we swap them over, and we've now completed our fourth pass.
We can now be sure that Weetabix, Sugar Puffs, Fruit 'n' Fibre,
Crunchy Nut Clusters and Cornflakes are all in the correct order.
The GCSE specification states that you must be able to understand the main steps of each algorithm,
understand any prerequisites of an algorithm,
apply the algorithm to a data set
and identify an algorithm if given the code for it.
However, you're not required to remember the code for these algorithms.
In the rest of this video, we will work through the pseudocode of the algorithm.
While it's important and you need to be able to spot this code,
don't get too worried about remembering it line for line.
So, we start by setting n to the length of the list
and we initialised our swapped flag to true.
We then enter a WHILE loop, which we keep running as long as n is greater than zero
and we're still making swaps.
We set our swapped flag to false,
and we decrement the number of items to check by 1, as our list is zero-indexed.
We enter a FOR loop to run up until n.
In other words, check every item.
We use an IF statement to check an item with its adjacent item.
If the item is greater than the one we're comparing it to
then it needs to be swapped.
Now, we use a temporary variable in order to perform a direct swap and set our swapped flag to true.
We know that algorithms are some of the hardest parts of any computer science specification,
so we've written a book called Essential Algorithms for A Level Computer Science, which is available on Amazon.
While the title of the book suggests this is only for A Level,
you can see here from the examination board mapping page
that we have chapters which cover every algorithm you're required to know for the GCSE.
This book then would be perfectly appropriate for you to use
and also to take on to A Level should you choose to carry on studying the subject.
Every chapter is presented in the same way.
We introduce the algorithm from a high-level perspective and provide a link to our videos.
We then lay out the algorithm in simple-structured English so you can get your head around it.
We illustrate the algorithm in the form of a diagram and then provide an example of stepping through it.
All of these steps are designed to really get you to understand the algorithm before we present you with pseudocode.
After the pseudocode, we present you with actual code written in both Python and Visual Basic,
which you could type in and try for yourself.
(uplifting piano jingle)