Bubble Sort

Part One: Understanding the basics

You may already have a good idea of how a bubble sort works. A bubble sort compares In terms of thinking about their structure we can easily replicate a bubble sort using a flowchart.

Take a look at the folk dance video to gain a better idea of how a bubble sort works.

Bubble sorts use what we call a flag, the flag tells us that a swap has been made. If we take the example on the folk dance video the flag is raised whenever a swap is made. If the flag is lowered then we go back to beginning of the list and make another pass. The flag is a boolean value (meaning it is true/false).

Part Two: Bubble sort flowchart

A flowchart can be used to represent a bubble sort. It is a useful starting point when beginning to think about how we can code a bubble sort.

Task 1: Create a flowchart for a bubble sort. If this is too hard use the template in the image to the right or check out this Lucid Chart template. If you want to edit this you'll need to install the Lucid Chart Google App and make a copy.

Task 2a: Sort this list using a bubble sort, recording each step of the process

Fish, Dog, Elk, Ape, Bear, Cat

Task 2b: Look at the two lists below, which list will be sorted first and why?

List A: Bear, Cat, Dog, Elk, Fish, Ape

List B: Fish, Ape, Bear, Cat, Dog, Elk

Figure 1

Figure 2

Figure 3

Figure 4

Part Three: Bubble sort Psuedo code

Let's take a look at the key things a bubble sort needs to be able to do:

move through a list one item at a time
compare two items
swap two items

Figure 1

Line 1: i represents the position of the item that is being checked, i=1 is the first item in the list. The second part of this code means that we only go up to the last but one item in the list, this is because there is nothing to compare the last item in the list to.

Figure 2

complete

Figure 3

Line 3: Imagine you have two jars, 1 containing water and the other orange juice. If you wanted to swap the contents of these jars you would need a third empty jar. This is where we make use of the variable named temp.

Let's take two numbers, 5 and 3 and work through lines 2 through 5.
List [i] = 5 and List [i+1] = 3

Line 2: 5 is greater than 3 so...
Line 3: temp = 5
Line 4: List [i] = 3
Line 5: List [i+1] = 5

So, by working through this code and using a temp variable we can see how the two numbers (items in a list) have now swapped position.

Figure 4

Here we start to add the final pieces of code, quite a lot happens in this step.

Line 1: We set our flag to true so that our loop will execute at least once

Line 2: The loop will execute as long as the flag is true

Line 3: The flag is now set to false before our for loop begins

Line 9: If a swap is made our flag is set to true so that the programme will loop once more. Remember if no swap is made then the list is in the correct order.

Part Four: Bubble sort in Python

Task 4a: Using the Psuedo code from task three write a programme that uses a bubble sort to order a list of numbers.

If you are feeling stuck then use the video to the right to help you.

Task 4b: As an extension use this CSV file to read, sort, display and write an ordered list (using a bubble sort).

Part Five: Bubble sort in Scratch

Believe it or not Scratch is not just a tool used by primary school students! By using Scratch you can apply your knowledge of how a bubble sort works to an interactive environment.

Task 5: Create a simple game that collates a score for each player. Once 3 or more players have played the game use a bubble sort to order the top scores of the players.

Task 5b: Make use of cloud variables in order to allow for cloud stored top scores. This will mean that top scores are saved as opposed to forgotten after each session.