AQA GCSE Computer Science June 2022 Paper 1, Question 12: the bubble sort trace table

AQA 8525 June 2022 Paper 1, Question 12: trace a bubble sort on a three item array, swap by swap, then say what the algorithm is for and why looping to 2 breaks it. The full table, the six marks explained, and the sort to run.

Past paper questionAQA 8525/1BJune 2022 Paper 18 marksTrace table

Question 12 of the AQA GCSE Computer Science June 2022 Paper 1 (8525/1B, the Python paper) is a bubble sort in disguise. The paper never says so: you trace twelve lines of pseudo-code (6 marks), then say what the algorithm is for (1 mark) and why an earlier version of it failed (1 mark).

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

The question in short

An array, arr, starts as c, b, a.

An outer loop runs i from 0 to 1. Inside it, an inner loop runs j from 0 to 1. On each pass, if the item at j + 1 is less than the item at j, the two are swapped, using a variable called temp to hold one of them for a moment.

The trace table has columns for arr[0], arr[1], arr[2], i, j and temp. The starting values c, b, a are filled in.

How a swap works

Three lines, always in this order:

1. temp ← arr[j] saves the left item.
2. arr[j] ← arr[j + 1] copies the right item over the left.
3. arr[j + 1] ← temp puts the saved item on the right.

So each swap writes three new values in the table: one in temp and two in arr.

Work it through

i = 0, j = 0. Compare arr[1] (b) with arr[0] (c). b is less than c, so swap. temp is c. The array is now b, c, a.

i = 0, j = 1. Compare arr[2] (a) with arr[1] (c). a is less than c, so swap. temp is c again. The array is now b, a, c.

i = 1, j = 0. Compare arr[1] (a) with arr[0] (b). a is less than b, so swap. temp is b. The array is now a, b, c.

i = 1, j = 1. Compare arr[2] (c) with arr[1] (b). c is not less than b. No swap, and nothing new to write except j.

The finished trace table

Where the six marks are

• i and j both starting at 0;
• the rest of the i and j columns: i is 0, 1 and j is 0, 1, 0, 1;
• the temp column: c, c, b;
• the first swap: arr[0] becomes b and arr[1] becomes c;
• the second swap: arr[1] becomes a and arr[2] becomes c;
• the third swap: arr[0] becomes a and arr[1] becomes b.

Values can go on different rows so long as the order down each column is clear. Quotation marks round the letters are ignored.

Parts 2 and 3

What is the algorithm for? It sorts the array into alphabetical order. "Bubble sort" gets the mark too.

Why did looping to 2 fail? With j = 2 the algorithm looks at arr[j + 1], which is arr[3]. The array only has positions 0, 1 and 2. It would try to use an index that does not exist.

Where the marks are lost

• Leaving temp out. It has a column, so it has a mark. Every swap writes to it.
• Writing c only once in temp. The second swap stores c again. (The mark scheme lets a missing middle c go, but do not rely on that.)
• Swapping when nothing should move. On the last pass c is not less than b.
• Resetting j wrongly. The inner loop starts again from 0 every time the outer loop moves on.

Run it

The same sort in Python, printing the array after every comparison. LAST is the number both loops run to.

from bugbot import *
connect()

# the loops run from 0 to LAST. The paper's earlier attempt used 2
LAST = 1

arr = ["c", "b", "a"]
print("i j  arr")
for i in range(0, LAST + 1):
    for j in range(0, LAST + 1):
        if arr[j + 1] < arr[j]:
            temp = arr[j]
            arr[j] = arr[j + 1]
            arr[j + 1] = temp
            print(i, j, arr, "swapped, temp =", temp)
        else:
            print(i, j, arr, "no swap")

To see a bubble sort on a longer list, and a robot that sorts real sensor readings, do the lesson linked below.

Questions

What is the answer to AQA GCSE Computer Science 2022 Paper 1 Question 12.1?

The array goes from c b a to b c a, then b a c, then a b c. The temp column is c, c, b. The i column is 0, 1 and the j column is 0, 1, 0, 1.

What is the purpose of the algorithm in Question 12?

It sorts the three letters into alphabetical order. It is a bubble sort.

Why is a temporary variable needed to swap two values?

Copying one value over the other destroys the second value. The temporary variable keeps a copy of it so that it can be put back in the other place.

Why do the loops in a bubble sort stop one short of the end of the array?

Each pass compares an item with the one after it. If the loop reached the last position, there would be no item after it, and the program would try to read outside the array.

More from this paper

• Question 10: Trace a REPEAT UNTIL loop with DIV, then compare it with WHILE 8 marks

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

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.