- [Craig] In this video, we're having a look at the insertion sort algorithm.
(uplifting piano jingle)
Before we dive into working through an example of this algorithm, let's summarise its key features.
The insertion sort inserts each item into its correct position in a data set one at a time.
It is a useful algorithm for small data sets.
It's particularly useful for inserting items into already sorted lists.
It is usually replaced by more efficient sorting algorithms for large 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 set 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.
The unsorted part of the list is being hidden in each step, but of course, all the items are still there.
The green items are the sorted part of the list and the orange items are the ones we are currently sorting and comparing,
and what we're going to do is insert each item into its correct place in the sorted list.
So, as you can see here with the first step, Sugar Puffs is the only item currently in the sorted list,
so for now, it's in the correct place.
Now, we check Crunchy Nut Clusters to Sugar Puffs.
Sugar Puffs is greater than Crunchy Nut Clusters, so we move it up a slot.
Crunchy Nut Clusters gets inserted into the currently occupied slot by Sugar Puffs.
We move on and compare Weetabix to Sugar Puffs.
Weetabix is greater than Sugar Puffs, so it's already in the right place.
We move on and compare Fruit 'n' Fibre with Weetabix.
Fruit 'n' Fibre is less than Weetabix, so we need to move Weetabix up one.
Fruit 'n' Fibre is less than Sugar Puffs, so we need to move Sugar Puffs up one.
Fruit 'n' Fibre is greater, however, than Crunchy Nut Clusters, so we've found its place and we can insert it here.
We move on and we compare Cornflakes with Weetabix.
Cornflakes is less than Weetabix, so we need to move Weetabix up one.
Cornflakes is also less than Sugar Puffs, so we need to move Sugar Puffs up one.
Cornflakes is less than Fruit 'n' Fibre, so we need to move Fruit 'n' Fibre up one.
And Cornflakes is less than Crunchy Nut Clusters, so we need to move Crunchy Nut Clusters up one.
We've now found the correct position for Cornflakes, so we insert it.
What we've got is our finished and sorted data set.
The GCSE specification states that you must be able to understand the main steps of each algorithm,
understand any prerequisites for 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'll work through the pseudocode for the algorithm.
While it is important and you need to be able to spot this code,
don't get too worried about remembering it line for line.
Now, the algorithm might seem a bit complex due to the way we had to explain it in the example,
but it's deceptively simple when we have a look at the actual code.
So, we use a FOR loop to check every item in the list.
The current item is the index we're starting with,
and the current position is the bottom of the list.
We enter a WHILE loop, which runs while the position is greater than zero
and the item in the list underneath us is greater than the current item.
The item at the current position becomes the item underneath it, swapping them over.
Once we've found the position of the new item in the list, we insert it.
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 onto 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)