AQA GCSE Computer Science sample Paper 1, Question 7: the bubble sort trace table

AQA 8525 sample assessment material, Paper 1 Question 7: a bubble sort on 4, 1, 6 with nested WHILE loops and a swapsMade flag. Its data type, why the identifier matters, which statement is false, and the six mark trace table. With the sort to run.

Past paper questionAQA 8525/1BSample Paper 110 marksTrace table

Question 7 of AQA's sample assessment material for GCSE Computer Science Paper 1 (8525/1B, the Python paper) is built round a bubble sort written with two WHILE loops and a flag. Three short parts (4 marks), then a trace table (6 marks).

We do not copy the paper here. Open it beside this page: AQA 8525 Paper 1B sample question paper (PDF). When you have finished, check the sample mark scheme too.

The question in short

arr is [4, 1, 6]. swapsMade starts false. An outer loop runs while swapsMade is false. Inside, swapsMade is set to true, i is set to 0, and an inner loop runs while i is less than 2: if arr[i+1] is less than arr[i], the two are swapped through t and swapsMade is set back to false. Then i goes up by 1.

So the outer loop keeps going until a whole pass makes no swap.

Parts 1 to 3

  • 7.1 The data type of swapsMade: Boolean.
  • 7.2 Why swapsMade beats s: it describes what the variable is for, which makes the algorithm easier to understand and maintain. Two marks: the reason and its effect.
  • 7.3 The false statement: "The algorithm uses a named constant." There is none. It does use indefinite iteration (WHILE) and nested iteration.

Part 4: the trace table

Outer pass 1. swapsMade becomes true, i is 0. Is arr[1] (1) less than arr[0] (4)? Yes: t is 4, the array becomes [1, 4, 6], swapsMade is false. i becomes 1. Is arr[2] (6) less than arr[1] (4)? No. i becomes 2. Inner loop ends.

Outer pass 2. swapsMade is false, so round again: it becomes true, i is 0. No swap at 0. i is 1. No swap. i is 2. Inner loop ends, swapsMade is still true, outer loop ends.

arr[0] arr[1] arr[2] swapsMade i t
4 1 6 false
true 0
1 4 false 4
1
2
true 0
1
2

One mark each for the three arr columns (the third only if the first two are right), the swapsMade column, the i column and the t column.

Where the marks are lost

  • Stopping after the first pass. A swap was made, so the flag is false and the outer loop runs again. The second pass, with no swaps, is what ends it.
  • Missing swapsMade going true at the top of each pass. It flips true, then back to false if a swap happens.
  • Writing 6 in arr[2] as a change. It never changes.
  • i going to 3. The inner loop stops when i is 2.

Run it

The same sort in Python, printing the state after every comparison. Change the array and count the passes.

With 4, 1, 6: one swap in pass 1, none in pass 2, sorted. Try 6, 4, 1 for three passes.
The program
from bugbot import *
connect()

arr = [4, 1, 6]
swapsMade = False
passes = 0
while swapsMade == False:
    swapsMade = True
    passes = passes + 1
    i = 0
    while i < 2:
        if arr[i + 1] < arr[i]:
            t = arr[i]
            arr[i] = arr[i + 1]
            arr[i + 1] = t
            swapsMade = False
        print("pass", passes, "i", i, arr, "swapsMade", swapsMade)
        i = i + 1
print("sorted in", passes, "passes:", arr)
Put this demo on your own site

Paste it into a school website, Moodle, Google Sites or a blog. More options on the embed page.

Questions

What is the answer to AQA sample Paper 1 Question 7.4?

arr goes from 4, 1, 6 to 1, 4, 6 after one swap, with t holding 4. swapsMade goes false, true, false, true. i goes 0, 1, 2, 0, 1, 2.

What is the swapsMade flag for?

It records whether the last pass changed anything. A pass with no swaps means the array is sorted, so the outer loop can stop.

Why is a meaningful identifier better than a single letter?

It tells the reader what the variable holds or does, so the code is easier to understand, test and change later.

More from this paper

Every AQA 8525 question we have worked · Guide: Trace tables explained

Learn it step by step

  1. F5.7 Bubble sort Algorithms
  2. F13.2 Trace tables Exam preparation
  3. F1.6 Variables, constants and assignment Programming basics
Open the lessons

This is our own explanation of a published exam question. It is not written or endorsed by AQA, and the question paper and mark scheme remain AQA's copyright. Read them on AQA's site with the links on this page.