Blog My Wiki!

Here’s a bubble sort I knocked up to help teach bubble sorts in Year 9. Before we get to this point we will have looked at Hungarian folk-dancing bubble sorts, done a bubble sort ourselves in class with human numbers and planned one out in a flow chart.

There are loads of Python bubble sort code examples online, but to be honest, none of them made much sense to me. The one thing I discovered doing this was that the best way to learn how to code a bubble sort, is to code your own. And the same must surely apply to my students…

Note this code is Python 2 (or Python 2 and a half) – I had to take the brackets out of the print statement on line 16 to get it to work in Trinket. The code below works in Python 3.

Click on the ‘play’ button to see it run, change the numbers, have a play…

This is probably not a ‘pure’ bubble sort – it stops as soon as it runs through the line of numbers without making any swaps. I think a pure bubble sort just keeps chugging though every line until every possible pair has been swapped, like the first example here. But I like teaching the point of the computer knowing when to stop.

You could also use this for teaching Boolean variables as it uses
sorted = False
while not sorted:
It will keep looping until sorted = True. I think this is nice, readable English-like example of this kind of iteration and control.

It works like this: as long as the list of numbers is ‘not sorted’, it keeps scanning through the list comparing every pair of numbers. If it finds that the first number in the pair, numberList[i], is bigger than the next, numberList[i+1], it swaps them over. When it finds it can run through the list without making a single swap, the list becomes sorted and the program stops.

This is how it works in more detail:

numberList = [89, 23, 56, 45, 17, 42, 100, 76, 1, 34]
sorted = False
while not sorted:

These lines set up the list of numbers – you can use any list of any length and it should still work. Try it! It sets a Boolean variable called sorted to have the value False (as the list is not sorted, or we don’t know it’s sorted). Then it starts a loop running which keeps going until the sorted variable is True.

    swaps = 0
    for i in range(len(numberList)-1):

This sets a variable called swaps to 0 at the start of each scan of the list. We use it to count how many swaps have been made on each run through the numbers. Line 14 starts a ‘for loop’ running that will have the variable i acting as an index for the numbers of the list we’re going to compare. We could go through it 9 times, but we want this code to work for a list of any length, so the number of comparisons to make is set by using len(numberList) – the length of the list, minus 1 because we don’t want to compare the 10th and 11th numbers when there’s no 11th number.

        if numberList[i] > numberList[i+1]:
            temp = numberList[i]
            numberList[i] = numberList[i+1]
            numberList[i+1] = temp
            swaps = swaps + 1

Lines 17 to 22 are where the comparison happens. If a number is bigger than the following number, they are swapped. I think in Python you can directly swap variables or items in a list, but for readability and my sanity, I’ve stored the 1st number in a temporary variable called temp. Then the second number gets written into the first number’s place in the list, and the temp variable (holding the first number) gets written into the second number’s place. As we’ve made a swap, the swaps counter gets increased by 1. That line could also read swaps += 1.

    if swaps == 0:
        sorted = True

Line 26 tests, at the end of a run through the list, if no swaps were made. If so, the list must be sorted, so we set sorted to be True and the while not sorted: loop magically vanishes in a puff of logic. The program then says the list is sorted, prints the shiny new list and stops running. Phew!

It’s got loads of extra lines to show the sort in progress, and it’s slowed down by pausing half a second per comparison. You can strip those lines out for students to type their own shorter version like this:

Compare the two to see just how fast the sort really is.

You could also get students to add code to count how many passes, swaps or comparisons are made, then see how bubble sorts behave with different types of lists: a reversed list, a random list, a nearly-sorted list. Then they could move on to comparing bubble sort with other sort algorithms.

And if you want to show a bubble sort in Scratch, try this one I made. It makes a very satisfying ‘pop’ sound when it makes a swap, so you can hear the smaller numbers bubbling to the top of the list:

The Scratch web site also has some other types of sort here.