AQA GCSE Computer Science Paper 1 (1C), June 2025: Question 6

✅ Complete Traced Table

Fill each row only when a swap occurs:

Green highlighted cells indicate the adjacent pairs swapped in that row.

📐 Step-by-Step Execution (Pass 1)

1. Compare 45 & 23: 45 > 23 → SWAP .
   List: [23, 45, 78, 55, 49] (Row 1 filled)
2. Compare 45 & 78: 45 < 78 → No swap.
3. Compare 78 & 55: 78 > 55 → SWAP .
   List: [23, 45, 55, 78, 49] (Row 2 filled)
4. Compare 78 & 49: 78 > 49 → SWAP .
   List: [23, 45, 55, 49, 78] (Row 3 filled)

🧠 Exam Technique & Guidance

• Read the trigger condition: "Show the new order every time the order has changed". Do not write a row if two items are compared and not swapped.
• One swap per row: A common misconception is writing only the state at the end of each full pass. That only gets 1 mark out of 3.
• Self-check: The final printed row already had [23, 45, 49, 55, 78] . Notice that in Pass 2, 55 and 49 swap to reach this final state.

❌ Common Errors

• Skipping intermediate swaps: Showing the list after each complete pass through the array rather than after every individual swap.
• Sorting elements all at once: Writing down what the sort "should look like" instead of mechanically following adjacent pair comparisons.

✅ Mark Scheme Criteria

• MP1: Correctly sorting pairs: [23, 45] and [55, 78] (or grouping from right-to-left: [45] , [23, 78] , [49, 55] ).
• MP2: Correctly leaving 1 element on its own after sorting pairs ( [49] or [45] ).
• MP3: Correctly combining into 3 or 4 sorted elements (e.g. [23, 45, 55, 78] with [49] , or [23, 45] with [49, 55, 78] ).

💡 How "Merging" Works

Merge sort uses Divide and Conquer. Because 5 elements cannot divide evenly, one item remains alone. When two ordered lists are merged, the algorithm compares the first available items of each sub-list and inserts the smaller item into the new list.

✅ Advantage of Bubble Sort (1 Mark)

State any one of:

• It is simpler to code / requires fewer lines of code.
• It can be quicker for small lists (or already nearly sorted lists).
• It uses less memory / sorts in place (merge sort requires additional auxiliary memory to store split sub-lists).

✅ Disadvantage of Bubble Sort (1 Mark)

State any one of:

• It does not sort large lists as quickly as merge sort.
• It is significantly less efficient on larger datasets (time complexity O(n²) vs O(n log n)).

❌ Common Pitfall: Unqualified Answers

The examiner strictly notes: NE (Not Enough) for just writing "Bubble sort is simple" or "It's easy". You must specify that it is simple to code / program / implement.

🧠 Exam Technique Tip

When asked to compare two algorithms, always mention the key computer science constraints: execution speed (time) and memory usage (space).

✅ Model Answer (2 Marks)

"A binary search is much faster and more efficient on average than a linear search [Mark 1] because it halves the remaining dataset with each comparison, requiring far fewer comparisons (a maximum of 12) compared to a linear search which might have to examine all 2500 items [Mark 2] ."

📐 The Math Behind 2500 Items

• Linear Search (Worst case): Must check all 2500 items sequentially.
• Binary Search (Worst case): Halves each time:
  2500 → 1250 → 625 → 313 → 157 → 79 → 40 → 20 → 10 → 5 → 3 → 2 → 1
  Since 2¹¹ = 2048 and 2¹² = 4096, it takes at most 12 comparisons!

💡 Why Binary Search Works Here

Binary search requires the list to be ordered. The question explicitly states the 2500 numbers are "stored in ascending order", meaning binary search can be applied directly without any preliminary sorting step.

❌ Common Errors

• Saying simply "it is faster" without stating why (halving the list / significantly fewer comparisons).
• Failing to reference the context (2500 elements or worst-case linear search checking everything).