Worksheet

F5.7 Bubble sort

Algorithms · GCSE · OCR J277 2.1.3, AQA 8525 3.1.4, Edexcel 1CP2 1.2.6 · about 15 min

What this lesson is about

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

• The algorithm
• In Python
• Hear it sort
• How much work it does

Questions 5 marks in all

1. [1 mark]What does this program print?

   items = [5, 2, 4, 1]
   for i in range(len(items) - 1):
       if items[i] > items[i + 1]:
           items[i], items[i + 1] = items[i + 1], items[i]
   print(items)

2. [1 mark]When can bubble sort stop early?

   1. AAfter a whole pass with no swaps
   2. BAfter the first swap
   3. CWhen it reaches the middle of the list
   4. DIt can never stop early

3. [1 mark]What does bubble sort compare?

   1. AEach pair of neighbouring items
   2. BEach item with the first item
   3. CThe middle item with the target
   4. DTwo halves of the list

4. [1 mark]A list of 6 items. How many comparisons does one pass of bubble sort make?

5. [1 mark]Why does a swap in pseudocode usually need a temporary variable?

   1. ACopying one item over the other would lose the first value
   2. BPseudocode has no lists
   3. CIt makes the sort faster
   4. DPython requires it

The 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]

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/f5-7-bubble-sort/
The simulator checks it and tells you when it passes. Nothing to install, no account.

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.