Lesson video

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

In this lesson, we're going to be looking at the code for the insertion sort and the bubble sort in Python.

For this lesson, you're going to need a pen, some paper, and you're going to need to remove any distractions that are going to get in the way of you focusing.

Once you've done that, let's begin.

True or false.

Choose whether each phrase for sorting algorithms is true or false.

I'll have a read of the phrase.

I'll give you a couple of seconds to have a think about it, or write down your answer to if you think it's true or false.

Bubble sort compares items next to each other in the list, and swaps them if they're in the wrong order.

True or false? That was true.

So it does compare them, and it does do them swaps.

Next, insertion sort compares an item from the unsorted sublist with the items in the sorted sublist and places them in the correct position.

True or false? That again was true.

Next, bubble sort is good at sorting large collections of unordered data.

True or false? The answer there was false.

The larger the list and in terms of being unordered means it's going to be more swaps that are taking part.

Next, bubble sort can be really fast at sorting data that is nearly in order.

True or false? That is true.

Why? Because there are going to be less swaps that are taking part.

Therefore, going to be faster.

Lastly, insertion sort is usually slower to execute than bubble sort on large unordered data lists.

True or false? That was false.

If you've got some wrong, do write the correct answer just so you're ready for it next time.

In this lesson, you will interpret the code for bubble sort and insertion sort, trace code for both sorting algorithms with input data, and identify factors that could influence the efficiency of a bubble sort implementation.

Code for bubble sort You need to be able to identify the code for a bubble sort algorithm, analyse improvements that could be made, and spot errors.

In the next slides, you will go over a step-by-step breakdown of one version of a bubble sort algorithm written in Python.

Define a new procedure for bubble sort.

What input data is needed for the algorithm's parameters? What we're going to need is items. The algorithm receives a list of items as a parameter.

Single pass.

So what is a single pass? It's when we iterate over the list of items. We're going to be using a for loop to perform the iteration.

Current is the index of the current item in the for loop.

So we've got for current in range and the values it ranges over will be determined after we specify the statements executed in the past.

So what are we doing here? We've got an if statement and we're going to compare the current item to the one next to it.

What happens if the items are in the wrong order? If they wrong order, we're going to swap the two elements.

As we can see here with the code highlighted on the left.

Which index value should current range over? So a hint here: How many items need to be compared in a single pass? How we think? So, with the bubble sort, if we had seven items that would only be six comparisons, because that last item is compared in that last comparison.

So therefore, the range here is going to be all the item indices, except the last one.

In the last iteration, the last two items will be compared.

Initialization: num_items stores the number of elements in the items list.

The statements for a single pass are placed inside a loop so that the process is repeated.

What is the condition for the while loop? For how long should the past be repeated? So here, each pass sets at least one or more items into the final position.

Use the passes variable to count the number of passes on repeat until all elements have reached their final position.

Task 1 - Code for bubble sort.

This task checks your understanding of the bubble sort algorithm written in Python.

Pause the video to complete your task.

Task 1 - Code for bubble sort Using the worksheet, complete Task 1.

Resume once you're finished.

Task 1 - Code for bubble sort Trace table solution As we can see here, we've got the solution for task one.

Compare it against what you've got, and if there are any discrepancies or if there's anything that you've got wrong, make a note of it.

So that hopefully next time you have a question like this, you don't make the same mistake.

Code for bubble sort: making improvements The previous version of the bubble saw algorithm in Python works, but it can be made more efficient.

You are going to look at two improvements to the code, which are reducing the number of comparisons after each pass and stopping once no swaps are made during a single pass.

Code for bubble sort: making improvements A tip here: Each pass sets at least one more item into its final position.

So when we're using the bubble sort, after the first pass, the item right at the end is in the correct position.

So improvement #1, there's no need for each pass to iterate all over the items. As the number of passes increases, the number of ordered elements increases and the range of indices for the current index decreases.

Improvement #2: So a tip here, if no elements are swapped during the pass the list is sorted.

So improvement #2, keep track of any swaps that were made and stop the algorithm once no elements are swapped in a single pass.

Swapped is a flag that will be that will be used to indicate whether any swaps were made during a single pass.

It is lowered at the star of each pass, and raised if a swap is made.

How can the swap flag be used so that more passes are performed only if the flag has been raised ? Let's take a look.

Continue passing through the list whilst swapped is true.

Next task is based on two improvements that can be made to the bubble sort algorithm.

Pause the video to complete your task.

Task 2 - Improving Bubble Sort Using the worksheet, complete Task 2.

There are two parts: reducing comparisons, and stopping when no swaps were made.

Resume once you're finished.

Code for bubble sort: making improvements solution So here, the text that's been highlighted, we can tell that's the, they're the improvements that we're going to be making.

Code for insertion sort You need to be able to identify the code for insertion sort, as well as bubble sort.

On the next slides, you'll go over a step-by-step breakdown of an insertion sort algorithm written in Python.

Code for insertion sort So we're starting off again in the exact same way.

We're defining a new procedure for insertion sort.

What input data is needed for the algorithms parameters? It's going to be the exact same.

We're going to need a list of items. The algorithm receives a list of items as a parameter.

Did you get that right? So both algorithms, when we searching or sorting, we need items that were going to be going through.

When we're searching, did you notice the difference was that we needed the the list of items and also the search item that we were looking for? So for sorting algorithms, we just need the list of items. Next, first_unordered is the index of the first item in the unordered section of the list.

The value of this item is stored.

This is the value that will be inserted at the appropriate position within the ordered section of the list.

Current is the index of the current item.

It starts at the last item in the ordered section of the list, right before the first unordered item.

Copy the value of the current item into the one next to it.

Imagine this as shifting an item to the right to make room for the new value to be inserted.

Repeat this shifting to the right process with the current index iterating over the elements of the ordered section of the list.

When will the shifting process stop so that the new value can be inserted? What do you think? Let's take a look.

As long as the current item is greater than the new item it needs to be shifted to make room for the new item or the new value.

Shifting also stops when the current index goes beyond the first list item.

Insert the new value after the point where the current index stopped.

The ordered section of the list is now extended by one item.

Perform this process iteratively, incrementing the first_unordered index in each iteration.

Because whenever we put in an item from the unordered list into the ordered list, the ordered list is going to get bigger.

Swapped is a flag that will indicate whether any swaps were made during a single pass.

Continue passing through the list while swapped is true Task 3 - Code for insertion sort The final task is based on the insertion sort algorithm in Python.

Pause the video to complete your task.

Task 3 - Code for Insertion Sort Using the worksheet, complete Task 2.

There are two parts: demonstrating insertion sort and an insertion sort algorithm.

Resume once you're finished.

Summary of bubble sort and insertion sort Bubble sort compares elements next to each other in the list and swaps them if they are in the wrong order.

A more efficient version of bubble sort uses a variable to flag where a swap was made during a single pass.

The insertion sort algorithm copies of values to be inserted in a variable at the start of each pass.

During the pass of an insertion sort, elements in the sorted part of the list are copied into the next position to make space for the value to be inserted.

Thank you very much for joining me on this lesson.

I hope you got a much better understanding of the Python code for the bubble sort and insertion sort algorithm.

If you want to share your work with Oak National you can do that via Instagram, Facebook, or Twitter, tagging @OakNational and #LearnwithOak.

Thank you very much for your time today and goodbye.

I am so glad.