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'll be learning about the efficiency of sorting algorithms and how we can use trace tables to track the steps of a sort.

Welcome to today's lesson from the unit Searching and Sorting Algorithms. This lesson is called Code Sorting Algorithms. And by the end of today's lesson, you'll be able to trace code for a sorting algorithm to identify factors which may impact efficiency.

Shall we make a start? We will be exploring these key words in today's lesson.

Trace table, trace table: an error checking method that steps through each line of code in a programme and records the state of the variables and conditions.

Efficiency, efficiency: in sorting algorithms, efficiency refers to how effectively an algorithm uses resources such as time and space while sorting a list of data.

Look out for these key words throughout today's lesson.

Today's lesson is broken down into two parts.

We'll start by tracing code for a bubble sort.

We'll then move on to explain how to improve the performance of a bubble sort.

Let's make a start by tracing code for a bubble sort.

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

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

We start by defining a new procedure for the bubble sort.

So we have def bubble_sort.

And then, we have a set of open brackets and a colon.

What input data is needed for the algorithm's parameters? Maybe pause the video whilst you have a think.

That's right, the algorithm is going to receive a list of items as a parameter.

So in the brackets, we've added the word items. A single pass iterates over the items in the list.

Current is the index of the current item.

The values it ranges over will be determined after we specify the statements executed in the past.

So on line 6, we've added a for loop, which says for current in range and we have a set of brackets and a colon.

We then need to compare the current item to the one next to it in the list.

So if items[current] is greater than items[current+1], the one next to it, and then we've got our colon on the end.

Jun says, "What happens if the items are in the wrong order though?" That's a really good question, Jun.

Let's have a look.

If the items are in the wrong order, we need to swap the two elements.

So we are going to use a temp variable to hold the value.

So temp is equal to items[current], items[current] is equal to items[current+1].

So we are swapping the next item in the list into the current position.

And then, we are swapping our temp variable back in into items[current+1].

So we've effectively done a swap there using a temp variable to hold the value whilst we do the swap.

Time to check your understanding.

Which index values should current range cover? So what should be inside our brackets in the for loop? As a hint, how many items need to be compared in a single pass? Maybe pause the video whilst you have a think.

That's right, all of the item indices except the last one need to be looped over.

So, num_items stores the number of elements in the items list, so we can use that.

So we now have for current in range.

And then, inside our bracket, num_items - 1.

So all of the items in the list but not the last one.

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

So you can see on line 4, we've added a while loop.

What is the condition for the while loop? How long should the passes be repeated? Maybe pause the video again whilst you have a think.

That's right, each pass sets at least one more item into its final position.

So we can use the passes variable to count the number of passes and repeat until all the elements have reached their final position.

So we've edited the while loop on line 4 now.

So it says while passes is less than num_items. And on line 13, we are incrementing the passes value.

So passes is equal to passes + 1.

And now we have our completed algorithm for a bubble sort.

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

So, well done.

An implementation of the bubble sort algorithm is shown in Figure 1.

So this is the same as the code we've just stepped through in the first part of today's lesson.

Read through the code to familiarise yourself with it again if you need to.

And don't worry if you don't understand all of it just yet.

The following questions will be based on executing the algorithm in Figure 1 when the items in the list are Laura, Izzy, Sam, Jun, and Andeep.

For part one, examine line 5 and state how many times the inner loop is performed on the list above.

How many pairs of items does every single pass examine? For part two, examine line 4 and state how many times the outer loop is performed on the list above.

How many passes does the algorithm make? Pause the video here whilst you look carefully at the code and complete the questions.

For part three, I'd like you to complete the trace table below for line 7 to 9 only of the algorithm.

The first line in the trace table contains the values for the current variable and the items list.

Pause the video whilst you complete the trace table.

How did you get on? Did you manage to answer the questions? Well done, let's have a look at some sample answers together.

So remember the following questions were based on executing the algorithm in Figure 1 when the items in the list were Laura, Izzy, Sam, Jun, and Andeep.

For part one, you were asked to examine line 5 and state how many times the inner loop is performed on the list above.

The inner loop will be executed four times.

The range will start at 0 and end at 4, exclusive of the end value.

So 5 - 1.

For part two, you were asked to examine line 4 and state how many times the outer loop is performed on the list above.

Again, that will be four times.

The condition passes less than num_items, evaluates to 1 less than 5 in the first instance, with passes incrementing by one after each iteration.

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

You were then asked to complete the trace table for line 7 to 9 only of the algorithm.

The first line of the trace table contains the values for the current variable and the items list.

So the first line, current 0, and then we have the items in the list: Laura, Izzy, Sam, Jun, and Andeep were already there for you.

On line 7, the temp variable is going to hold the value Laura.

On line 8, the list is going to become Izzy, Izzy, Sam, Jun, Andeep.

'Cause remember, we're copying Izzy across so that we can perform the swap.

On line 9, the list then becomes Izzy, Laura, Sam, Jun, and Andeep 'cause we copy the value from temp, which is Laura in this case, back into the correct position in the list.

Okay, so, so far we've traced code for a bubble sort.

We are now going to move on to explain how to improve the performance of a bubble sort.

The previous version of the bubble sort algorithm in Python works but it can be made more efficient.

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

Jun says, "How can the number of comparisons be reduced after each pass?" Maybe have a think about this question.

Do you know how the number of comparisons can be reduced? Ah, Sam says, "There's no need for each pass to iterate over all of the items. As the number of passes increases, the number of ordered elements increases." That's a really good point, Sam, well done.

Each pass of the bubble sort algorithm sets at least one more item into its final position.

So there's no need for each pass to iterate over all of the items again and again.

As the number of passes increases, the number of ordered elements increases and the range of indices for the current index decreases.

So you can see we've changed the for loop here.

So it now says for current in range, open brackets, num_items - passes, close our brackets and then our colon.

So it's using that passes variable to reduce the number of times it loops each time.

Jun says, "How do we stop the algorithm once no swaps are made during a single pass?" That's another really good question, Jun.

Maybe pause the video whilst do you have a think of the answer.

Ah, Sam says, "You can keep track of any swaps that were made and then stop the algorithm once no elements are swapped in a single pass." If no elements are swapped during a pass, then the list is sorted and we don't need to continue.

Swapped is a flag which will indicate if any swaps were made during a single pass.

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

So you can see on line 5, we are setting the swapped flag to false before the for loop.

We then change the flag to true if a swap is made on line 11.

Time to check your understanding.

Swapped is a flag which will indicate if any swaps were made during a single pass.

How can the swap flag be used so that more passes are performed only if the flag has been raised and the list is not sorted yet? Maybe pause the video here whilst you have a think.

Did you spot it? Well done, what we can do is we can change the condition of our while loop.

So on line 5, we now have while swapped is equal to true.

So we continue passing through the list while swapped is true and a swap was made during the previous pass.

If swapped is equal to false and no passes were made, then the algorithm will stop.

Which of the following are methods to improve the performance of a bubble sort? A, stopping once a swap is made in a single pass; B, stopping once no swaps are made during a single pass; or C, reducing the number of comparisons after each pass.

Pause the video whilst you have a think.

Did you select B and C? Well done, stopping once no swaps are made during a single pass and reducing the number of comparisons after each pass are both methods that can improve the performance of a bubble sort algorithm.

Okay, we are moving on to our second task of today's lesson.

One improvement that could be made to the bubble sort algorithm is to change the range of the inner loop on line 5 from num_items - 1 to num_items - passes.

Complete the table below for tracing the two expressions: num_items - 1 and num_items - passes when the items is a list of eight items. Pause the video whilst you have a go at the activity.

I'd now like you to explain how changing the range of the inner loop to num_items - passes increases the efficiency of the bubble sort algorithm compared to num_items - 1.

Pause the video whilst you answer the question.

How did you get on? Did you manage to complete the table and compare the two expressions? Great work, let's have a look at the example answers together.

So on the first pass, num_items - 1 will be 7 and num_items - passes will also be 7.

On the second pass, num_items - 1 will still be 7, whereas num_items - passes becomes 6 and that process is repeated.

So num_items - 1 always remains a 7 'cause it will go through every item in the list whereas num_items - passes decreases on each pass.

So you can see it goes down from 7 all the way down to 1 on the seventh pass of the algorithm.

You were then asked to explain how changing the inner loop to num_items - passes increases the efficiency of the bubble sort algorithm compared to num_items - 1.

Using the range num_items - passes means that as passes increase, the number of items that each pass iterates over decreases.

So each pass goes over fewer items. With the range num_items - 1, you can see that the number of items passed over remains constant or the same throughout.

Remember, if you want to pause the video here and make any changes to your answers, you can do that now.

Okay, we've come to the end of today's lesson, Code Sorting Algorithms, and you've done a fantastic job, so well done.

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

Code for sorting algorithms can be analysed by how efficient the algorithm is.

A trace table can be used to analyse an algorithm.

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

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

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