Lesson video

Hi, I'm Kashif your computer science teacher for the algorithms unit.

In this lesson, we're going to be looking at our second sorting algorithm which is the insertion sort, for this lesson, you're going to need a pen, some paper and you're going to need to move any distractions that are going to get in the way of you focusing, once you've done that, let's begin.

Where does this book go? Given a list of books with the authors names as below, where would you insert an additional book by George Orwell? So have a look at the authors below and have a think where you would insert a book by George Orwell? Do you have your answers? Let's check, so we would insert that book just after Roald Dahl, why? Because the authors names are ordered by surname and it's all alphabetical there, so the O in George Orwell is after the D and before the R.

In this lesson, you will insert an item into an ordered list of items, describe how insertion sort is used for ordering a list of items and perform an insertion sort to order a list containing sample data.

Inserting an item, in the previous activity, you probably wouldn't have added the new book to a random place in the list of books and then used a bubble sort to sort the order of the list, why is that? It would have taken too long, it would make more sense to make space for the new book and insert it into the correct position in the list, as you can see from the example above, 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, retrieve a card from the unsorted pile, make room for the card in the sorted list and then insert the card into the correct position in the list.

Using the instructions on the previous slide, you are going to insert a card into a sorted list of cards, for task one, you are going to fill in a table to show the list of cards after one insertion, pause the video to complete your task.

Task one, inserting an item, using the worksheet complete task one, resume once you're finished.

Inserting an item solution, so for the first question here, we had the four spades and we looked at the list and those we create space between the three spades and the six of spades, on the second question, we have the nine of spades and there was no room for in-between any cards, so we inserted it at the end of the list because we compared it to eight, nine is bigger than eight, so therefore we put it after the eight.

Insertion sort, the insertions 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 the items in the sorted sublist until is inserted into the correct position, on the next slides, you will see how the algorithm inserts one out of order item into the correct position in the list, in one pass of the algorithm.

Insertion sort, single pass, each number is hidden under a cup, the cups need to be sorted with the lowest value on the left, as we can see, we've got two lists there a sorted list and an unsorted list, 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 into the sorted list, so here cup five is the out of order item, copy the first out of order item into value, so we're copying the number 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 cup four in this instance, if the item or the current position is greater than value, so 80 is greater than 35, copy it into the next item, so you're copying 80 from under cup four to cup five and move on to the previous item in the list, if the item at the current position is greater than value, so 43 is greater than 35 copy it into the next item, so 43 is being moved from under cup three into cup four and move on to the previous item in the list, so now we're looking under cup two, if the item at the current position is not greater than value, so 21 is not greater than 35, value is ready to be inserted in the list, copy value into the item after the current position, one pass has now been completed, increasing the sorted sublist by one item.

Algorithm for one pass of the insertion sort, the instructions for executing one pass of insertion sort can be written as take a list where the first items are ordered and the rest are not, copy the first out order item into 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 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, finally, copy value into the item after the current position.

Insertion sort, multiple passes, now that you've seen how one pass of an insertion sort works, the next slides will go through multiple passes to show you how a complete insertion sort is executed, each value is hidden under a cup, the cups need to be sorted with the lowest value on the left, take a list of data to be sorted, let the unsorted sublist contain all the items except the first one, in the first 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, compare it to the items in the ordered list and 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, 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, compare it to the items in the ordered list and 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, 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, compare it to the items in the ordered list, and shift these items until the new item has been inserted into 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, retrieve the first out of order item, compare it to the items in the ordered list and shift these items until the new item has been inserted into the correct position, one pass has now been completed, increasing the sorted sublist by one item, in the next pass, the last remaining out of order item will be inserted at the appropriate position in the sorted list, retrieve the first out of order item, compare the item to the items in the ordered list and shift the items until the new item is inserted into the correct position, one pass has now been completed and the list of items is now ordered.

Algorithm for a complete insertion sort, the instructions for executing an insertion sort, can be seen or written as follows, take a list of data to be sorted, let the unsorted sublist contain all the items except the first one, repeat steps one to three, the pass until the unsorted list is empty, one, copy the first out of order item into value, 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 into the list, A, if the item at the current position is greater than value, copy it into the next item and move on to the previous item in the list, B, otherwise, value is ready to be inserted in the list, finally, copy value into the item after the current position.

Executing an insertion sort, complete the tasks on executing an insertion sort, pause the video to complete your task.

Task two, executing an insertion sort, using the worksheet complete task two, there are two parts, sorting a list of names and sought by cuisine, resume once you're finished.

Task two, executing an insertion sort solution, below, is the solution for each pass of the insertion sort, how did you get on? So if you were to compare your answers to what we've got here.

Brilliant.

Comparing insertion sort to bubble sort, you may have noticed that an insertion sort passes over the 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.

Summary of insertion sort, 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 list and places it in the correct position, people often perform an insertion sort when they're putting objects such as books or cards into order.

Thank you for joining me on this lesson, I hope you've got a better understanding of how the insertion sort works.

You can share your work with Oak National by using Instagram, Facebook, or Twitter tagging @OakNational and #LearnwithOak.

Thank you for your time today and hopefully I'll see you on the next lesson.

Goodbye.