Lesson video

Hello, my name is Mrs. Holborow, and welcome to computing.

I'm so pleased you've decided to join me for the lesson today.

In today's lesson, we are going to be investigating insertion sort.

We will see how one pass of the sort is performed and then perform an insertion sort to order a list.

Welcome to today's lesson from the unit, "Searching and sorting algorithms." This lesson is called "Insertion sort." And by the end of today's lesson, you'll be able to use an insertion sort to sort a list containing sample data.

Shall we make a start? We will be exploring these keywords throughout today's lesson.

Insertion sort.

Insertion sort, a sorting algorithm that progressively evaluates items in a list and inserts them into the correct place in an ordered sublist.

Sorted sublist.

Sorted sublist, sorted values held in the lower positions of the list.

Unsorted sublist.

Unsorted sublist, unsorted values held in the higher positions of the list.

Look out for these keywords throughout today's lesson.

Today's lesson is broken down into two parts.

We'll start by performing one pass of an insertion sort and then we'll move on to perform an insertion sort to order a list.

Let's make a start by performing one pass of an insertion sort.

Given a list of books with the author names as shown in the table, where would you insert an additional book by George Orwell? Maybe pause the video here whilst you have a think.

That's right.

You'd place the book between Roald Dahl and Patrick Rothfuss.

You probably wouldn't have added the book to a random place in the list and then performed a separate sort on the list.

It would make more sense to make space for the new book and insert it into the correct position in the list.

This is essentially how an insertion sort works.

Imagine you are sorting a pack of cards into order.

To add a card into the sorted list of cards, you would probably do something like, one, retrieve a card from the unsorted pile, two, make room for the card in the sorted list, and three, insert the card into the correct position in the list.

You have two groups of cards.

One group of cards is arranged in a sorted list, the other group of cards is in an unsorted pile.

So you can see in the sorted list, we have the cards two, four, five, seven, and eight.

In the unsorted pile, we have the card, the six of spades, at the top of the pile.

To insert the card, the six of spades, into the list, you would make a space between the five of spades and the seven of spades.

So we've made the space.

You would then insert the six of spades into the space you have created.

So now the sorted list contains the cards two, four, five, six, seven, and eight.

And the unsorted pile has the card, the ace of spades, at the top.

Time to check your understanding.

Describe what you think would happen to the list if you wanted to insert another card, the ace of spades, after you had inserted the six of spades.

Ace is considered low in this example.

Pause the video whilst you have a think.

How did you get on? The ace of spades would be inserted into the first position in the sorted cards.

All of the other cards in the sorted list would move along one to the right to make room for the ace of spades.

Did you have that as your answer? Well done.

The insertion sort algorithm works by grouping the items in a list into two parts, a sorted sublist and an unsorted sublist.

With each pass through the list, an item from the unsorted sublist is compared to items in the sorted sublist until it is inserted into the correct position.

In the next slides, you will see how the algorithm inserts one out-of-order item into the correct position in the list, i.

e.

, one pass of the algorithm.

The instructions for executing one pass of an insertion sort can be written as, one, take a list where the first items are ordered and the rest are not, two, copy the first out-of-order item into a value.

Repeat steps A to B starting from the last of the ordered items until no more items remain or value is ready to be inserted into the list.

A, if the item at the current position is greater than value, copy it into the next item.

Move on to the previous item in the list.

B, otherwise, value is ready to be inserted into the list.

Four, copy value into the item after the current position.

Each number is hidden under a cup.

The cups need to be sorted with the lowest value on the left.

So you can see the list is divided into two sublists, a sorted list on the left and an unsorted sublist on the right.

Take a list where the first items are ordered and the rest are not.

In each single pass, the first out-of-order item is inserted at the appropriate position in the sorted list.

Copy the first out-of-order item into value.

So we are copying 35 into value.

Taking a copy of the last out-of-order item is necessary.

As items are shifted to the right, to make room for the new value, the last item in the list will be overwritten.

Start with the last of the ordered items. So, current is 80.

If the item at the current position is greater than value, copy it to the next item.

Move on to the previous item in the list.

So we are copying it to the next item and then we're moving on to the previous item in the list.

Now, current is cup three, which contains 43.

If the item at the current position is greater than value, copy it to the next item, and then move to the previous item in the list.

So cup two is now current.

Cup two contains the value 21.

If the item at the current position is not greater than value, value is ready to be inserted into the list.

So we're inserting 35 in cup position three.

So we're copying the value into the item after the current position.

So now our sorted list contains the items 2, 21, 35, 43 and 80, and our unsorted list has reduced by one.

One pass has now been completed, increasing the sorted sublist by one item.

An insertion sort is partway through sorting the following list of items into ascending order, low to high.

So we have the sorted list 1, 23, 45, and the unsorted sublist 12, 46, 3, and 8.

The next item to insert is the number 12.

How many items will be moved when inserting this item into the correct position, including the item to insert 12? Is it A, one, B, two, or C, three? Pause the video whilst you have a think.

Did you select three? Well done.

In order to insert 12 into the sorted list, we would have to shift 23 and 45, and then move the item itself, the number 12.

Okay, we are moving on to our first task of today's lesson, and you're doing a fantastic job so far.

So, well done.

A teacher wants to sort their students' test scores so that the lowest score appears at the start of the list.

They use an insertion sort to sort the data.

The current state of the list is, so we have a sorted sublist containing 43, 49, and 64, and then we contain an unsorted sublist, which contains the values 51, 74, 68, and 70.

Write the steps to explain the next pass of the insertion sort.

Pause the video whilst you complete the activity.

How did you get on? Did you manage to write the steps of the insertion sort pass? Well done.

Let's have a look at a sample answer together.

One, take a list where the first items are ordered and the rest are not.

Two, copy the first out-of-order item into value.

So value is going to be equal to 51.

Three, start with the last of the ordered items, 64.

Four, if the item at the current position is greater than value, copy into the next item.

Five, move on to the previous item in the list, value 49.

Six, if the item at the current position is not greater than value, value is ready to be inserted into the list.

Seven, copy the value into the item after the current position.

So our sorted sublist now contains the items 43, 49, 51, and 64, and our unsorted sublist contains the values 74, 68, and 70.

Okay, we are now moving on to the second part of today's lesson, where we're going to perform an insertion sort to order a list.

Aisha says, "I have seen how an insertion sort inserts an item into a list that is mostly sorted.

But what if I have a list that isn't sorted at all?" That's a really good question, Aisha.

Well done.

Each number is hidden under a cup.

The cups need to be sorted with the lowest value on the left.

So we take a list of data to be sorted.

Let the unsorted sublist contain all the items except the first one.

So you can see cup one is sorted and cups two to six are unsorted.

In the first pass, the first out-of-order item will be inserted at the appropriate position of the sorted list.

Cup two is our first unsorted item and contains the value 21.

Retrieve the first out-of-order item.

Compare it to the items in the order list.

So 43 compared to 21.

Shift these items until the new item is inserted into the correct position.

So we've swapped 21 and 43.

Our sorted sublist now contains two items, 21 and 43.

One pass has now been completed, increasing the sorted sublist by one item.

In the next pass, the first out-of-order item will be inserted at the appropriate position in the sorted list.

This time, cup three.

Retrieve the first out-of-order item, the value two.

Compare it to the items in the ordered list.

Shift these items until the new item is inserted into the correct position.

So 21 and 43 are shifted up to make room for the value two.

One pass has now been completed, increasing the sorted sublist by one item.

In the next pass, the first out-of-order item will be inserted at the appropriate position in the sorted list.

Retrieve the first out-of-order item, cup four contains the value 80.

Compare it to the items in the ordered list.

Shift these until the new item is inserted into the correct position.

So we don't actually need to do any shifting here 'cause 80 is actually in the correct position.

One pass has now been completed, increasing the sorted sublist by one item.

In the next pass, the first out-of-order item will be inserted at the appropriate position in the sorted list.

Cup five contains the value three.

So we're going to retrieve that as the first out-of-order item.

We compare it to the items in the ordered list.

Time to check your understanding.

Where will the cup containing the number three shift to? Is it A, cup one, B, cup two, or C, cup four.

Pause the video whilst you have a think.

Did you say B, cup two? Well done.

The three is going to be inserted in between the two and the value 21.

So we shift these items until the new item is inserted into the correct position.

One pass has now been completed, increasing the sorted sublist by one item, and we only have one item left in our unsorted sublist now.

In the next pass, the last remaining out-of-order item will be inserted at the appropriate position in the sorted sublist.

We retrieve the first out-of-order item.

Cup six contains the value 35.

We compare it to the items in the ordered list and we shift these items until the new item is inserted into the correct position.

So the 35 is going between the value 21 and 43.

So our list is now sorted and contains the values 2, 3, 21, 35, 43, and 80.

One pass has now been completed and the list of items is now ordered.

Time to check your understanding.

What is the missing step from the full instructions for executing an insertion sort.

Take a list of data to be sorted.

Let the unsorted sublist contain all of the items except the first one.

Repeat steps one to three, the pass, until the unsorted list is empty.

One, there's the missing step.

Two, repeat steps A to B, starting from the last of the ordered items until no more items remain or value is ready to be inserted in the list.

A, if the item at the current position is greater than value, copy it into the next item.

Move on to the previous item in the list.

B, otherwise, value is ready to be inserted in the list.

Three, copy value into the item after the current position.

Pause the video whilst you have a think about the missing step.

Did you get the missing step? The missing step is to copy the first out-of-order item into value, because remember, it'll be overwritten.

You may have noticed that an insertion sort passes over a list, a similar amount of times to bubble sort.

However, an insertion sort usually involves fewer comparisons per pass.

This means that insertion sort is generally quicker to execute than bubble sort, especially on large data sets.

Okay, so we are moving on to the second part of today's lesson, and you've done a fantastic job so far.

So, well done.

For task B, we are going to perform an insertion sort to order a list.

Sam has created a programme that uses a file to store the names of people who have completed her game.

A sample of the data is shown in figure one.

So in figure one, we have a list of data which contains the names Sam, Jun, Izzy, Andeep, Laura, and Aisha.

Carry out an insertion sort on the on the data shown in figure one by filling in the table on the next slide.

Each row should show one pass of the algorithm and any elements that have changed position.

You should also shade or highlight the elements that are in the sorted sublist.

The initial sorted sublist and the first pass has been completed for you.

So let's see what they look like on the next slide.

So you can see at the top, we have the original data from figure one, and then we have the shaded sorted sublist.

So, Sam, in the first row of the table, is the sorted sublist because that contains the first item in the list.

We've then completed the first pass.

So you can see that Jun and Sam have swapped position, and Jun and Sam are now highlighted as the sorted sublist.

Continue the steps until you have completed the insertion sort on the original data.

Pause the video here whilst you complete the activity.

How did you get on? Did you manage to perform the insertion sort on the data? Well done.

Let's have a look at the sample answers together.

So remember, the first two rows of the table were completed for you.

So let's start by looking at row three.

So we now have Izzy, Jun, and Sam in our sorted sublist, and Andeep, Laura, and Aisha in the non-sorted sublist.

On the fourth row, we have Andeep, Izzy, Jun, and Sam in the sorted sublist, and Laura and Aisha in the unsorted sublist.

On row five, we have Andeep, Izzy, Jun, Laura, and Sam in the sorted sublist, and just Aisha in the unsorted sublist.

And then in the last row, we have the sorted data, which is Aisha, Andeep, Izzy, Jun, Laura, and Sam.

Remember, if you need to pause the video here and make any corrections, you can do that now.

Andeep is developing a programme for a food delivery service.

The system allows users to select from a list of cuisines from around the world.

A sample of data is shown in figure two.

So we have Persian, Greek, Indian, Thai, Nigerian, Italian, and Spanish.

For part one, state the cuisine that will be in the sorted sublist to start with when executing an insertion sort on the data shown in figure two.

For part two, show all of the stages of an insertion sort when applied to the data shown in figure two.

Pause the video whilst you complete the tasks.

How did you get on? Did you manage to complete the insertion sort? Well done.

Let's have a look at the sample answers together.

So for part one, you were asked to state the cuisine that will be in the sorted sublist to start with when executing an insertion sort on the data shown in figure two.

The cuisine that will be in the sorted sublist is Persian because this is the first item in the list.

For part two, you were asked to show all of the stages of an insertion sort when applied to the data shown in figure two.

Let's have a look at the sample answer together.

So you can see in the first row, we have Persian in the sorted sublist, and then we have Greek, Indian, Thai, Nigerian, Italian, Spanish.

Row two, we have Greek, Persian Indian, Thai, Nigerian, Italian, Spanish.

Row three, Greek, Indian, Persian, Thai, Nigerian, Italian, Spanish.

Row four, Greek, Indian, Persian, Thai, Nigerian, Italian, Spanish.

Row five, Greek, Indian, Nigerian, Persian, Thai, Italian, Spanish.

Row six, Greek, Indian, Italian, Nigerian, Persian, Thai, Spanish.

And then row seven, the final sorted list, which should be Greek, Indian, Italian, Nigerian, Persian, Spanish, and Thai.

Okay, we've come to the end of today's lesson, insertion sort, and you've done a fantastic job.

So, well done.

Let's summarise what we've learned together during this lesson.

An insertion sort groups the items of a list into two parts, a sorted sublist and an unsorted sublist.

The algorithm takes each item from the unsorted sublist, compares it to the items in the sorted sublist, and places it in the correct position.

People often perform an insertion sort when they are putting objects in order, like books or cards.

I hope you've enjoyed today's lesson, and I hope you'll join me again soon.

Bye.