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're going to 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 Coding Sorting Algorithms, and by the end of today's lesson, you'll be able to trace code for a sorting algorithm and identify factors which may impact efficiency.

Shall we make a start? We will be exploring these keywords 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 variables and conditions.

Efficiency.

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

Look out for these keywords throughout today's lesson.

Today's lesson is broken down into three 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.

And then we'll finish up by tracing code for an insertion 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 pass.

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're going to use a temp variable to hold the value.

So temp = items[current] items[current] = items[current+1].

So we are swapping the next item in the list into the current position, and then we're swapping our temp variable back in to 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 brackets, 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're incrementing the passes value.

So passes = 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 lines 7-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 lines 7-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 because 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 because we copy the value from temp, which is Laura in this case, back into the correct position in the list.

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

We're 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 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're 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 swapped 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 line 5, we now have while swapped == True.

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

If swapped = 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're 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 because 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, so we've traced code for a bubble sort and we've explained how we can improve the performance of a bubble sort, we're now going to move on to trace code for an insertion sort.

As well as bubble sort, you need to be able to identify the code for insertion sort.

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

So we start by defining a new procedure for the insertion sort.

This is very similar to what we did for the bubble sort, def insertion_sort and then we have a set of open brackets at the moment 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, exactly the same as our bubble sort.

The algorithm receives a list of items as a parameter.

First_unordered is the index item of the first item in the unordered section of the list.

The value is the item that is stored.

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

So we have value = items[first_unordered].

So the first unsorted item is going to become our value.

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.

We then copy the value of the current item into the one next to it.

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

So item[current+1] = items[current].

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

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

When will the shifting process stop so that the new value can be inserted? Maybe pause the video whilst you have a think That's right, as long as the current item is greater than the new value, it needs to be shifted to make room for the new value.

The shifting also stops when the current index goes beyond the first list item and there are no more elements left to shift.

So our while loop condition is while current is greater or equal to 0 and items[current] is greater than value.

We then insert the new value after the point where the current index stopped.

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

So we have items[current+1] is equal to value.

We perform this process iteratively, incrementing the first unordered index in each iteration, extending the ordered section of the list.

So you can see on line 2 we've added the variable num_items, which is equal to the length of the list items. And then on line three we've added a for loop.

So for first_unordered in range(1, num_items):.

Time to check your understanding.

Choose whether each phrase for a bubble and insertion sort is either true or false.

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

Insertion sort compares an item from the unsorted sublist to the items in the sorted sublist and places it in the correct position.

Bubble sort is good at sorting large collections of unordered data.

Bubble sort can be really fast at sorting data that is nearly in order.

And insertion sort is usually slower to execute than bubble sort on large unordered datasets.

Pause the video here whilst you think carefully about each one and state whether it's true or false.

How did you get on? Let's go through the sample answers together.

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

That's true.

Insertion sort compares an item from the unsorted sublist to the items in a sorted sublist and place in the correct position.

That's true again.

Bubble sort is good at sorting large collections of unordered data.

That's false.

Bubble sort is more efficient on smaller sets of data normally.

Bubble sort can be really fast on sorting data that is nearly in order.

That's true.

Insertion sort is usually slower to execute than bubble sort on large unordered data sets.

Again, that's false, insertion sort tends to be quicker on larger sets of unsorted data.

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

An implementation of the insertion sort in Python is shown in figure 2.

This is the same example that we've stepped through in today's lesson.

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

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

For part one, state the number of times the outer loop would repeat if the items was a list of 10 items. And as a hint, the first value of range is the start value and the second value is the stop value.

For part two, describe what line 3 does during each iteration of the outer loop.

And then for part three, explain the purpose of the condition items[current] greater than value, which is on line 6 of the code.

Pause the video here whilst you complete the questions.

For part four, I'd like you to complete the trace table below for lines 6-9 only of the algorithm.

The first line in the trace table contains the items list after two passes of the algorithm.

So you can see we have Andeep, Laura, Sam, Jun, Izzy.

The variables value and current after executing lines 4 and 5 have also been included in the table for you.

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 the sample answers together.

For part one, state the number of times the outer loop would repeat if items was a list of 10 items. The outer loop would repeat nine times.

The range would start at 1 and stop immediately when it reaches 10.

For part two, you were asked to describe what line 3 does during each iteration of the outer for loop.

Line 3 stores the value of each unsorted item in sequence starting from index 1 since the first item is already considered to be in the sorted sublist.

For part three, you are asked to explain the purpose of the condition items[current] greater than value on line 6.

This condition is used to compare the element at the current index to the value to be inserted.

The condition will evaluate to true whilst the element at the current index is greater than the insertion value, meaning that the correct position has not yet been found.

You would then asked to complete the trace table for lines 6-9 only of the algorithm.

And remember, the first line in the trace table contained the items list after two passes of the algorithm.

So let's start on line 7.

The items list is going to contain Andeep, Laura, Sam, Sam, and Izzy because remember, Jun has been copied out into value.

On line 8, current becomes 1.

And then we go back to line 7 and the items list becomes Andeep, Laura, Laura, Sam, Izzy.

Go back to line 8 and current is set to 0.

And then on line 9, our list becomes Andeep, Jun, Laura, Sam, Izzy.

So, Jun has been placed in the correct position, which is in the index 1 of the items list.

Okay, we've come to the end of today's lesson coding sorting algorithms, and you've done a fantastic job today, 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 bubble sort uses a variable to flag when a swap has been made during a single pass.

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

During a pass of the 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.

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

Bye.