Bubble sort — AQA A-Level Computer Science
Bubble sort is an elementary comparison-based sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. In AQA A-Level Computer Science, it serves as a foundational example of an in-place algorithm with O(n^2) worst-case time complexity and O(1) auxiliary space complexity.
Bubble sort explained
This statement requires you to know how bubble sort works, to trace its execution step by step on a small list, and to analyse its time complexity.
Read the full explanation
Bubble sort repeatedly passes through the list, comparing adjacent elements and swapping them when they are out of order, so that the largest unsorted value moves to the end on each pass. Tracing means recording the list after each comparison or pass, for example sorting [5, 3, 4] gives [3, 5, 4] after the first swap, then [3, 4, 5] after the second. Analysis examines how many comparisons are made as n grows. With n elements, the outer loop runs up to n−1 times and the inner comparisons shrink each pass, giving about n(n−1)/2 comparisons, so the worst-case and average-case time complexity is O(n²). The best case, where the list is already sorted and an early-exit flag stops the algorithm after one pass, is O(n).
Your focus
- Know and be able to trace and analyse the time complexity of the bubble sort algorithm.
Which command word is this?
Follow the algorithm systematically step-by-step, recording variable states or array configurations at precisely specified intervals without skipping steps.
Bubble sort exam tips
Topic Overview
Bubble sort is one of the standard sorting algorithms covered in the AQA A-Level Computer Science specification under algorithms and data structures. It functions by sequentially evaluating adjacent elements in an array or list, swapping their positions whenever they appear out of order until the entire structure is sorted.
Understanding Bubble sort provides critical insight into time-space trade-offs, algorithm efficiency, and Big-O notation. It provides a baseline comparison against more advanced divide-and-conquer algorithms, such as Merge sort and Quick sort, which achieve better average-case runtime efficiency.
Key Concepts
- →Adjacent comparisons: The core mechanism of comparing item i with item i+1 and conditionally swapping them.
- →Passes: A complete traversal of the unsorted segment of the list, at the end of which the largest remaining element bubbles to its final position.
- →Optimization flag: A boolean variable (e.g., 'hasSwapped') that monitors whether any swaps occurred during a pass, permitting early exit in O(n) time.
- →Time complexity bounds: Best-case O(n) with flag optimization, average-case O(n^2), and worst-case O(n^2).
- →Space complexity: O(1) auxiliary space because it sorts in-place without generating copies of the list.
Marking Points
- Traces the algorithm by recording the list state after each swap or pass and identifies the element that is fixed at the end of each pass.
- Explains that the inner loop length reduces by one on each pass, leading to roughly n(n−1)/2 comparisons.
- States that the worst-case and average-case time complexity is O(n²).
- Recognises that with an early-exit check on a sorted list the best case is O(n).
Examiner Tips
- 💡Write out the list after each pass when asked to trace, so each step can be followed and credited.
- 💡Give the complexity for the case the question asks about, and say which case it is.
- 💡Explain the shrinking inner loop when justifying an O(n²) result.
- 💡Always state the array state after each full pass rather than after individual swaps unless the exam question explicitly asks for a step-by-step swap trace.
- 💡If asked to write pseudocode, remember to reset your boolean swap flag to False at the start of every outer loop pass.
- 💡When comparing sorting algorithms, highlight that Bubble sort's primary advantage is its low memory footprint and simplicity, while its main drawback is its quadratic time complexity on large datasets.
Common Mistakes
- Describes the number of passes as fixed at n; correct by noting the inner loop shortens after each pass, reducing the work.
- Gives O(n) as the complexity for all cases; correct by stating that the worst case is O(n²) and O(n) applies only to the best case with early exit.
- Traces the swaps without recording the list state, so the trace cannot be checked; correct by writing the full list after each pass or swap.
- Believing that Bubble sort always takes the exact same number of passes regardless of initial ordering; in reality, an early-exit flag allows the algorithm to terminate after a single pass if the data is already sorted.
- Confusing space complexity with time complexity, asserting that Bubble sort is memory-heavy; it is actually memory-efficient with O(1) auxiliary space.
- Assuming Bubble sort compares elements across the entire array at arbitrary distances, confusing it with Insertion sort or Shell sort; it only ever compares strictly adjacent items.
Revision Plan
- 1Day 1-2: Manually trace Bubble sort with paper and pen using an array of 5-6 values, noting element comparisons and swaps per pass.
- 2Day 3-4: Write and test the standard and optimized Bubble sort algorithms in Python or pseudocode using an early termination flag.
- 3Day 5-6: Derive the arithmetic progression formula (n(n-1)/2) to mathematically prove the O(n^2) worst-case time complexity.
- 4Day 7: Complete AQA past paper questions focusing on trace tables and algorithm comparisons against Merge sort and Insertion sort.
Exam Question Types
- 📋Trace tables and state outputs: Showing the array contents after each pass for a specific dataset.
- 📋Pseudocode writing or completion: Implementing nested loops, swap mechanics, and early termination flags.
- 📋Algorithm evaluation and comparison: Explaining when Bubble sort is suitable compared to Merge sort or Quick sort with reference to Big-O notation.
Command Word Expectations (AQA)
Follow the algorithm systematically step-by-step, recording variable states or array configurations at precisely specified intervals without skipping steps.
Provide clear reasoning linking the mechanics of the algorithm (e.g., nested loops) directly to the resulting characteristic (e.g., O(n^2) time complexity).
Identify both similarities and differences between two algorithms (e.g., Bubble sort vs Merge sort), explicitly addressing time complexity, space complexity, and suitability.
How Students Lose Marks (Examiner Pitfalls)
Step-by-Step Worked Solutions
Question: Trace the execution of an optimized Bubble sort on the array [7, 3, 9, 2, 5]. Show the state of the array at the end of each complete outer pass, and state the total number of comparisons made.
- 1.Step 1: Identify initial state: [7, 3, 9, 2, 5], length n = 5.
- 2.Step 2: Pass 1 comparisons (4 comparisons total): - Compare 7 and 3: swap -> [3, 7, 9, 2, 5] - Compare 7 and 9: no swap -> [3, 7, 9, 2, 5] - Compare 9 and 2: swap -> [3, 7, 2, 9, 5] - Compare 9 and 5: swap -> [3, 7, 2, 5, 9] State after Pass 1: [3, 7, 2, 5, 9]. (Element 9 is in its final position).
- 3.Step 3: Pass 2 comparisons (3 comparisons total): - Compare 3 and 7: no swap -> [3, 7, 2, 5, 9] - Compare 7 and 2: swap -> [3, 2, 7, 5, 9] - Compare 7 and 5: swap -> [3, 2, 5, 7, 9] State after Pass 2: [3, 2, 5, 7, 9]. (Elements 7, 9 are in final positions).
- 4.Step 4: Pass 3 comparisons (2 comparisons total): - Compare 3 and 2: swap -> [2, 3, 5, 7, 9] - Compare 3 and 5: no swap -> [2, 3, 5, 7, 9] State after Pass 3: [2, 3, 5, 7, 9].
- 5.Step 5: Pass 4 comparison (1 comparison total): - Compare 2 and 3: no swap -> [2, 3, 5, 7, 9]. No swaps occurred during Pass 4, so the algorithm terminates.
- 6.Step 6: Calculate total comparisons: 4 + 3 + 2 + 1 = 10 comparisons.
Question: Explain why Bubble sort has a worst-case time complexity of O(n^2) and an auxiliary space complexity of O(1).
- 1.Step 1: Define time complexity in terms of the number of operations relative to input size n. In the worst case (a reverse-ordered list), the algorithm must execute (n - 1) passes.
- 2.Step 2: Calculate the number of comparisons: Pass 1 requires (n - 1) comparisons, Pass 2 requires (n - 2), continuing down to 1 comparison on the final pass. The sum of integers from 1 to (n - 1) is (n(n - 1)) / 2 = (n^2 - n) / 2. In Big-O notation, lower-order terms and coefficients are ignored, yielding O(n^2).
- 3.Step 3: In this reverse-order scenario, every comparison also results in an element swap, leading to O(n^2) swaps.
- 4.Step 4: Define space complexity in terms of additional memory. Bubble sort sorts the list 'in-place', meaning it modifies the original array directly.
- 5.Step 5: Only a constant amount of temporary memory is required for loop index counters and the swap temporary variable, regardless of the size of n. Therefore, auxiliary space complexity is O(1).