Lesson video

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

In this lesson, we're going to be looking at our first sorting algorithm which is the Bubble Sort.

For this lesson, you're going to see the 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.

Finding a surname.

Given the two lists above, which list do you think it would be easier to find a surname in, and why do you think that? Write your answers down.

Okay.

Looking at the list, list two would be easier to find a surname in because, the data has been arranged alphabetically.

In this lesson, you will identify why computers often need to sort data, traverse a list of items, swapping the items that are out of order and perform a Bubble Sort to order a list containing sample data.

Why is sorting important? Humans like to categorise and order things to greater or lesser degrees.

In supermarkets, the fresh vegetables and fruit will have been placed together with bakery goods somewhere else in the shop and tin goods in another aisle.

Sorting is usually done to make searching faster.

The main concept behind these next few lessons regarding sorting algorithms, is to get the idea through that, we need to sort data in order to allow searching to be done much faster.

As you saw previously with the binary search.

Think about any list of names.

They will often be presented alphabetically to make it easier to find an individual.

In computer science, sorting algorithms are used to arrange the items of 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? write your answers down? Okay.

Let's have a look.

Why is sorting important? Choosing which sorting algorithm to use depends on certain factors, such as how efficient an algorithm is on large sets of data, or how easy it is to implement and test.

In this lesson, you will explore how to execute an algorithm called Bubble Sort.

Bubble Sort.

A Bubble Sort algorithm works by repeatedly going through a list, comparing adjacent items and swapping the items if the items are in the wrong order.

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

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

In the next slides, you'll see how the algorithm swaps adjacent items that are in the wrong order during one pass of a Bubble Sort.

Bubble Sort one pass.

Each number is hidden under a cup.

The cups need to be sorted with the lowest value on the left.

So cup one needs to have the lowest value, cup nine needs to have the highest value.

So we're taking a list of data to be sorted.

Here is the initial order of the cups.

When you're executing a Bubble Sort, you will only be comparing two items at a time.

Out from the first item in the list.

So we're looking at the current position.

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

As we said, we're only going to be comparing two items at time.

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

So we can see the current position, we've got 43, the next position, we've got 21, 43 is greater than 21, therefore we're going to be swapping them across.

Go to the next item in the list.

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

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

So here we've got 43, which is greater than two, therefore we're going to be swapping them.

Go to the next item in the list.

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

If the item at the current position is greater than the one next to it, swap the items. Here we can see that 43 is not greater than 50.

So we're not going to be doing any swaps here.

Go to the next item in the list.

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

If it's greater, we're going to be doing a swap.

So you can see the pattern that's being played here.

We're going to be repeating these same steps over and over again.

So 50 is greater than three, therefore we're swapping it.

And we're looking at the next item.

We're comparing it.

We've got 50.

We've got 80.

50 is not greater.

We can leave it where it is.

We're looking at the next item.

We're comparing it.

This time, 80 is greater than 35, so we do need to swap it.

We're looking at the next item.

We're going to compare it.

80, 64.

80 is greater, so we're going to have a swap here.

Next item in the list.

Let's compare it.

Got 80, and we've got seven.

80 is greater, therefore, we're going to swap it with seven.

One pass has now being completed.

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

So what we're trying to say there is, you're going to be keep doing additional passes until no swaps are done in the previous pass.

As you can see, the highest number here was 80 and now it's at the end of the list.

So that 80 is in the correct position.

We have our original list, and we have the list after one pass.

A single pass results in the largest element reaching its final position at the end of the list, as it is always going to be greater than the, as it will always be greater than the elements that are next to it.

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 correct place.

Algorithm for one pass of a Bubble Sort.

The instructions for performing one pass of a Bubble Sort can be written as, one, take a list of data to be sorted, two, repeat steps a to c for all the items in the list starting with the first one.

So a, compare the item at the current position to the one next to it.

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

C, go to the next item in the list.

Task one, one pass of a Bubble Sort.

You are now going to perform one pass of a Bubble Sort on a list of cards.

Pause the video to complete your task.

Task one, one pass of a Bubble Sort.

Using the worksheet, complete task one.

Resume once you're finished.

One pass Bubble Sort solution.

So as you can see on the solution, we can see the items that are being compared because they've been highlighted.

How did you get on? Okay, let's move on.

Comparing elements with Bubble Sort.

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

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, that is the number of elements minus one.

Fully execute a Bubble Sort, you need to keep passing through the list until all elements are in order.

How do you know that the list has been sorted after you've finished a pass? If no swaps are made during a single pass, that means that none of the elements are out of order, and the algorithm can stop executing.

Algorithm for a complete Bubble Sort.

The instructions for executing a Bubble Sort in full can be written as, take a list of data to be sorted, repeat step one, the pass, until no swaps are made.

Repeat steps a to c for all items in the list starting from the first one.

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

If the item at the current position is greater than the one next to it, swap the item within the list, and then go to the next item in the list.

Task two, executing a Bubble Sort.

You are now going to be executing a Bubble Sort.

Pause the video to complete your task.

Task two, executing a Bubble Sort.

Using the worksheet complete task two.

There are two parts, sorting a list of names and sorting by cuisine.

Resume once you're finished.

Executing a Bubble Sort, task one solution.

Below is the solution for each pass of the Bubble Sort in the first task.

So as we can see, at the end of the first pass, Vicky is at the end, at the end of the second pass, we've got Toby and Vicky, third pass, Rhonda Toby Vicky, fourth pass George Fatima Rhonda Toby Vicky.

We've got that in order.

How did you get on? Okay, let's continue.

Executing a Bubble Sort.

You may have noticed in the last activity that after each pass, the largest value is in its proper place.

This means that you would never need to check the largest value again once a pass has been completed.

You can therefore reduce the number of comparisons by one after each pass to improve the efficiency of the algorithm.

Summary of Bubble Sort.

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

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

Thank you for joining me on this lesson.

You can share your work with us @OakNational.

Be sure to ask a parent or carer, and you can do this on Instagram, Facebook or Twitter tagging @OakNational and #LearnwithOak.

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

Goodbye.