Bubble sort

Passes and swaps, stopping early, and hearing a tune become a scale.

F5.7AlgorithmsGCSE15 min

Binary search needs sorted data, and so do leaderboards, timetables and the robot's "nearest first" lists. Sorting puts items in order. This lesson and the next two meet the three sorting algorithms on the GCSE specifications, and this one you can hear: the robot plays a list of notes, and as the sort works the tune turns into a scale.

The algorithm

Bubble sort compares neighbours:

1. Go through the list from the start, comparing each pair of neighbouring items.
2. If a pair is in the wrong order, swap them.
3. When you reach the end, that is one pass. The largest item has "bubbled" to the end.
4. Do another pass, and another, until a whole pass makes no swaps. Then the list is sorted.

Watch one pass on [5, 2, 4, 1]:

After one pass, 5 is in its final place at the end. The next pass only needs to sort the rest.

In Python

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

items = [5, 2, 4, 1, 3]
n = len(items)
swapped = True
passes = 0
while swapped:
    swapped = False
    for i in range(n - 1):
        if items[i] > items[i + 1]:
            items[i], items[i + 1] = items[i + 1], items[i]     # swap the pair
            swapped = True
    passes = passes + 1
    print("after pass", passes, ":", items)
print("sorted:", items)

Run this in the simulator

items[i], items[i + 1] = items[i + 1], items[i] swaps two items in one line. In most languages, and in exam pseudocode, a swap needs a spare variable:

temp = items[i]
items[i] = items[i + 1]
items[i + 1] = temp

The swapped flag is what lets bubble sort stop early: a pass with no swaps proves the list is sorted, so there is no point doing more.

Hear it sort

Each pass plays the whole list as notes. At first it is a jumble; by the end it is a rising scale:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

notes = [392, 262, 523, 330, 294]

def play(ns):
    for note in ns:
        tone(note, 0.12)
    wait(0.3)

play(notes)
swapped = True
while swapped:
    swapped = False
    for i in range(len(notes) - 1):
        if notes[i] > notes[i + 1]:
            notes[i], notes[i + 1] = notes[i + 1], notes[i]
            swapped = True
    play(notes)
print(notes)

Run this in the simulator

How much work it does

For a list of n items, each pass makes n - 1 comparisons, and in the worst case, a list in reverse order, it needs n - 1 passes. A reversed list of 10 items is about 90 comparisons; of 1,000 items, about a million. Bubble sort is easy to understand and to write, and fine for short or nearly sorted lists, but slow for big ones. On a list that is already sorted, it makes one pass, finds no swaps, and stops.

Task: sort the tune

Sort notes = [392, 262, 523, 330, 294, 440, 349, 494] with bubble sort, written yourself (no sort or sorted). Then print sorted: <the list> and play every note of the sorted list for 0.2 seconds.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

notes = [392, 262, 523, 330, 294, 440, 349, 494]

Challenges

1. Count the comparisons and swaps, and print both at the end. Try a list that is already sorted, and one in reverse order.
2. Change the sort to put the notes in descending order: a falling tune.
3. Each pass can stop one item earlier than the last, because the end of the list is already sorted. Add that improvement and count the comparisons saved.