Bubble sort

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

F5.7AlgorithmsGCSE15 min

Covers OCR J277 2.1.3 Searching and sorting algorithms · AQA 8525 3.1.4 Sorting algorithms · Edexcel 1CP2 1.2.6 Standard sorting and searching algorithms

Do this lesson in the simulator

Print it: worksheet (PDF) · answers (PDF) · as a web page

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:

Go through the list from the start, comparing each pair of neighbouring items.
If a pair is in the wrong order, swap them.
When you reach the end, that is one pass. The largest item has "bubbled" to the end.
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]:

Compare	Swap?	List after
5 and 2	yes	[2, 5, 4, 1]
5 and 4	yes	[2, 4, 5, 1]
5 and 1	yes	[2, 4, 1, 5]

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.

Each pass carries the biggest grey item along to the end of the grey part, so the green part grows from the right. After pass 3 the list is sorted, but bubble sort only knows that when pass 4 makes no swaps.

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. In the worst case, a list in reverse order, it needs n - 1 passes to sort it, and the version above makes one more pass to find no swaps. A reversed list of 10 items takes 10 passes of 9, which is 90 comparisons; of 1,000 items, 999,000, 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.

The red line bends upwards: double the list from 10 to 20 items and a reversed list needs 380 comparisons instead of 90, about four times as many. A list that is already sorted takes one pass and stops, so its line stays low.

In the exam

You may be asked to show the state of a list after each pass of bubble sort, to count the passes or swaps, to write it in pseudocode or code, or to compare it with merge sort. Show the whole list after each pass, and remember the early stop: bubble sort ends after a pass with no swaps.

OCR 2.1.3

OCR's standard sorting algorithms are bubble sort, merge sort and insertion sort. You need their main steps and to apply them to a set of data.

AQA 3.1.4

AQA's sorting algorithms are bubble sort and merge sort. You should understand how each works and compare them: bubble sort is simpler and uses less memory, merge sort is more time efficient on large lists.

Edexcel 1.2.6

Edexcel's standard sorting algorithms are bubble sort and merge sort, and you should be able to show them working on a list of data.

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

Count the comparisons and swaps, and print both at the end. Try a list that is already sorted, and one in reverse order.
Change the sort to put the notes in descending order: a falling tune.
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.

Past paper questions on this

Real exam questions that test this, each worked through with a program you can run.