Answers

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)

   Answer:

   [2, 4, 1, 5]

   One pass: the largest item, 5, bubbles to the end.

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
   Answer: A. A pass with no swaps proves the list is already sorted.

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
   Answer: A. It compares neighbours and swaps them if they are in the wrong order.

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

   Answer: 5. n - 1 pairs of neighbours in a list of n items.

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
   Answer: A. temp = a; a = b; b = temp keeps both values. Python's a, b = b, a does it in one line.

The task: sort the tune

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

from bugbot import *
connect()
notes = [392, 262, 523, 330, 294, 440, 349, 494]
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
print("sorted:", notes)
for note in notes:
    tone(note, 0.2)