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 bubble sort algorithm.

We will see how one pass of the bubble sort operates and then perform a bubble sort to order a list.

Welcome to today's lesson from the unit Searching and sorting algorithms. This lesson is called "Bubble sort," and by the end of today's lesson, you'll be able to perform a bubble sort to order data in a list.

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

Let's take a look at them now.

Bubble sort.

Bubble sort: a sorting algorithm that repeatedly compares pairs of values within a list and swaps them if they are out of order.

Pass.

Pass: a complete traversal of a list.

Look out for these keywords in today's lesson.

Today's lesson is split into two parts.

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

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

Consider these two lists.

Which list do you think it would be easier to find a surname in? And why do you think that? Maybe pause the video whilst you have a think.

Alex says, "I think list two would be easier because the surnames are in alphabetical order." I think you are right, Alex.

I think it would be easier to find a surname, especially if the list was much longer.

In computer science, sorting algorithms are used to arrange the items in a list in a particular order.

For example, from lowest to highest.

Computers frequently need to sort large amounts of data based on a certain attribute.

Can you think of any examples when computers need to sort data? Perhaps pause the video whilst you have a think.

Ah, Aisha says, "Sorting a list of files by name or file size." That's a really good example, Aisha.

Well done.

Sam says, "Arranging search results in a search engine from highest to lowest ranking." That's another really good example, Sam.

Alex says, "Sorting data in a spreadsheet column from lowest to highest." Again, another really good example.

Well done, Alex.

Choosing which sorting algorithm to use depends on certain factors, such as how efficient it is on large sets of data, how easy it is to implement and test, how much memory the algorithm may require, and how the data is formatted.

The bubble sort algorithm works by repeatedly going through a list, comparing adjacent items, and swapping the items if they're in the wrong order.

Each time the algorithm goes through the list is called a pass.

The pass through the list is repeated until the list is sorted.

The instructions for performing one pass of a bubble sort can be written as: one, take a list of data to be sorted; two, go to the next item in the list, at the start this will be the first item; three, compare the item at the current position to the one next to it; four, if the item at the current position is greater than the one next to it, swap the items within the list; five, repeat steps two to four until you reach the last item in the list.

Each number is hidden under a cup.

The cups need to be sorted with the lowest value on the left, so the lowest value should be in cup one.

The first step is to take a list of data to be sorted.

So we've got our list cups one through to nine.

Each number is hidden under a cup.

So just for our purpose here, we can see the numbers and the order that they are in.

Here is the initial order of the list.

However, when you are executing a bubble sort, you'll only be comparing two items at a time.

We start from the first item in the list, which in this case is cup one, and this becomes the current item.

We compare the item at the current position to the one next to it.

So we compare 43 to 21 in this case.

If the item at the current position is greater than the one next to it, swap the items in the list.

So 43 is greater than 21, so we're going to swap them over.

We then go to the next item in the list, cup two.

This now becomes current.

Compare the item at the current position to the one next to it.

So this time we have 43 and 2.

Remember, we swapped cup one and cup two, so cup two now contains 43.

If the item at the current position is greater than the one next to it, swap the items in the list.

43 is greater than 2, so we're going to swap them.

Go to the next item in the list.

Cup three becomes current.

Compare the item at the current position to the one next to it.

This time we compare cup three and four, 43 and 50.

If the item at the current position is greater than the one next to it, swap the items in the list.

Note here, we don't need to make a swap because 43 is not greater than 50.

Go to the next item in the list, cup four.

Compare the item at the current position to the one next to it.

So we are comparing 50 and 3.

If the item at the current position is greater than the one next to it, swap the items in the list.

50 is greater than 3, so we're going to swap them.

Go to the next item in the list.

Cup five becomes current.

Compare the item at the current position to the one next to it.

So 50 is compared to 80.

If the item at the current position is greater than the one next to it, swap the items within the list.

Time to check your understanding.

What will be the next step of the algorithm? Would it be A, swap the items within the list, or B, go to the next item in the list? Maybe pause the video whilst you have a think.

That's right.

Did you say B? We'll go to the next item in the list because 50 is not greater than 80, so no swap is needed here.

We go to the next item in the list, which is cup six.

We compare the item at the current position to the one next to it, so cup six and seven.

If the item at the current position is greater than the one next to it, swap the items in the list.

80 is greater than 35, so we're going to swap.

We go to the next item in the list, cup seven.

We compare the item at cup seven to the one next to it, which is cup eight.

So we're comparing 80 and 64.

If the item at the current position is greater than the one next to it, we are going to swap the items in the list.

80 is greater than 64, so we're going to complete a swap.

We then go to the next item in the list, cup eight.

We compare cup eight and nine, which is 80 and 7.

If the item at the current position is greater than the one next to it, then we're going to swap the items. 80 is greater than 7, so we perform the swap.

We've then reached the end of our list.

So you can see we've completed one pass of the algorithm, but notice the data isn't in the correct order just yet.

One pass has now been completed.

If any swaps were made in this pass, then keep passing through the list until no swaps are made.

Time to check your understanding.

How many swaps were needed on the initial pass of the list? Was it A, five; B, six; or C, seven? Have a look carefully at the data and see what you think.

Did you select B, six? Well done.

Six swaps were made on the first pass of the algorithm.

So we can see the data after the first pass.

A single pass of the bubble sort algorithm results in the largest element reaching its final position at the end of the list, since it'll always be greater than the element it's next to.

This means that the next pass doesn't need to check the final pair of elements as you know the largest element is in the right place.

So you can see here the value of 80 is in its final position after the first pass.

Okay, time to move on to our first task of today's lesson.

I'd like you to perform one pass of a bubble sort on the cards.

You need to show each comparison and whether any swaps were made.

The cards should be ordered from lowest to highest, where ace is considered low.

The first comparison has been done for you.

So the initial order was six, four, five, two, eight, ace, which is going to be low, so one in this case, seven, and then three.

After the first comparison, the list is four, six, five, two, eight, ace, seven, three.

And I've highlighted cards four and six to show that a swap has been made.

How did you get on? Did you manage to complete one pass of the cards? Well done.

So here's an example which shows the first pass of the algorithm.

So the first two rows have been completed for you.

The third row should be four, five, six, two, eight, ace, seven, three, and the five and six have been swapped.

Fourth row should be four, five, two, six, eight, ace, seven, three.

The fifth row should be four, five, two, six, eight, ace, seven, three.

The sixth row should be four, five, two, six, ace, eight, seven, three.

The seventh row should be four, five, two, six, ace, seven, eight, three.

And then the final row should be four, five, two, six, ace, seven, three, eight.

So we've completed one complete pass, but the data isn't in a complete order just yet.

Okay, we are now going to move on to perform a bubble sort to order a list entirely.

In the last activity, your cards should have been in this order after one pass.

So four, five, two, six, ace, seven, three, eight.

It should have taken you seven comparisons to pass over these eight cards.

The number of comparisons made in a single pass is always equal to the number of pairs you pass over, e.

g.

the number of elements in the list minus one.

Sam says, "One pass has not sorted the cards in the correct order though." You are right, Sam, we're going to have to perform more than one pass to order this data.

To fully execute a bubble sort, you need to keep passing through the list until all of the elements are in order.

How do you know that the list has been sorted after you've finished a pass? Maybe pause the video whilst you have a think.

That's right, if no swaps are made during a single pass, then that means none of the elements are out of order and the algorithm can stop executing.

Well done.

So the instructions for executing a bubble sort in full can be written as: one, take a list of data to be sorted; two, go to the next item in the list, at the start this will be the first item; three, compare the item at the current position to the one next to it; four, if the item at the current position is greater than the one next to it, swap the items within the list; five, repeat steps two to four until you reach the last item in the list; and then six, repeat the pass, which is going to be steps one to five, until no swaps are made.

Describe what happens to the largest card in the list after one pass.

How might this affect the number of comparisons that need to be made in the next pass? Pause the video whilst you have a think.

A single pass results in the largest card reaching its final position at the end of the list, since it'll always be greater than the card it is next to.

This means that the next pass doesn't need to check the final pair of cards as you know the largest card is in its right place.

Bubble sort is one of the slowest algorithms for sorting data and performs poorly in real world use, especially on large collections of data.

However, you can improve the efficiency of the bubble sort algorithm by stopping once no swaps were made during a single pass and reducing the number of comparisons by one after each pass.

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

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

A sample of data is shown in Figure 1.

So Figure 1 contains a list of names, which starts with Sam, then Jun, then Izzy, then Andeep, then Laura, and then finally, Aisha.

Carry out a bubble sort on the data shown in Figure 1 by filling in the table below.

Each row should show one pass of the algorithm and any swaps that have been made.

The first pass has been completed for you.

Pause the video whilst you complete the activity.

How did you get on performing the bubble sort? Well done.

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

So the first pass had been completed for you.

So the third pass should be: Izzy, Andeep, Jun, Aisha, Laura, Sam.

The fourth pass should be: Andeep, Izzy, Aisha, Jun, Laura, and Sam.

The fifth pass should be: Andeep, Aisha, Izzy, Jun, Laura, Sam.

And then the final pass should be: Aisha, Andeep, Izzy, Jun, Laura, and Sam.

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

Andeep is developing a programme for a food delivery service.

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

A sample of data is shown in Figure 2.

So the list starts with Persian, followed by Greek, then Indian, Thai, Nigerian, Italian, and Spanish.

For part one, state the number of comparisons that need to be made during the first pass of a bubble sort when applied to the data shown in Figure 2.

For part two, state the cuisine that will be in the correct position after one pass when executing a bubble sort on the data shown in Figure 2.

And then for part three, show all of the stages of a bubble sort when applied to the data shown in Figure 2.

Pause the video whilst you complete the tasks.

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

For part one, you were asked to state the number of comparisons that need to be made during the first pass of a bubble sort when applied to the data shown in Figure 2.

Six comparisons would need to be made.

For part two, you were asked to state the cuisine that would be in the correct position after one pass when executing a bubble sort on the data shown in Figure 2.

The cuisine would be Thai.

That's because that will be in the final position in the list, so will be sorted after the first pass.

For part three, you were asked to show all of the stages of a bubble sort when applied to the data shown in Figure 2.

Let's have a look at that now.

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

The next pass: Greek, Indian, Nigerian, Italian, Persian, Spanish, and Thai.

And then the final pass: Greek, Indian, Italian, Nigerian, Persian, Spanish, and Thai.

Did you have those passes? Well done.

Okay, we've come to the end of today's lesson, "Bubble sort." Let's summarise what we've learned together during today's lesson.

The bubble sort algorithm works by repeatedly going through a list, comparing adjacent items and swapping the items if they're in the wrong order.

Each time the algorithm goes through the list is called a pass.

The pass through the list is repeated until no more changes are made on a pass.

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

Bye.