4.3.5.1 Bubble sort Quiz: AQA Computer Science, Unit 3

The 20 questions

1. What is the time complexity of bubble sort?

   • O(n log n)
   • O(n)
   • O(n^2)
   • O(log n)

2. In bubble sort, what happens to adjacent items that are out of order?

   • They are swapped
   • They are merged
   • They are ignored
   • They are deleted

3. What is guaranteed after completing the first full pass of bubble sort?

   • Smallest item positioned
   • List fully sorted
   • Median item positioned
   • Largest item positioned

4. What is the worst-case time complexity of the bubble sort algorithm?

   • O(n)
   • O(n log n)
   • O(n^2)
   • O(log n)

5. Which items are compared and potentially swapped during a pass of bubble sort?

   • Random pairs
   • First and last
   • Opposite elements
   • Adjacent pairs

6. Which sorting algorithm is included in the specification as a particularly inefficient example?

   • Binary tree sort
   • Merge sort
   • Dijkstra sort
   • Bubble sort

7. Bubble sort is applied to [5, 1, 4, 2, 8]. What is the list after the first pass?

   • [1, 5, 4, 2, 8]
   • [1, 2, 4, 5, 8]
   • [1, 4, 2, 5, 8]
   • [5, 1, 4, 2, 8]

8. Bubble sort is applied to [5, 1, 4, 2, 8]. What is the list after two passes?

   • [1, 2, 4, 5, 8]
   • [2, 1, 4, 5, 8]
   • [1, 4, 2, 5, 8]
   • [1, 2, 4, 8, 5]

9. How many swaps does bubble sort perform in total while sorting [5, 1, 4, 2, 8]?

   • 4
   • 3
   • 5
   • 2

10. How many comparisons are made in the first pass of bubble sort on a list of 10 items?

    • 8
    • 9
    • 45
    • 10

11. How many comparisons does a complete bubble sort of n items make without an early-exit check?

    • n + 1
    • log2 n
    • 2n
    • n(n - 1) / 2

12. With an early-exit check that stops when a pass makes no swaps, how many passes are needed to confirm an already sorted list of 10 items?

    • 10
    • 1
    • 9
    • 2

13. If the number of items in a bubble sort doubles, by what factor does running time increase?

    • 2 times
    • 16 times
    • 4 times
    • 8 times

14. How many swaps does bubble sort need to sort the reverse-ordered list [4, 3, 2, 1]?

    • 3
    • 10
    • 6
    • 4

15. For a list of 100 distinct items in reverse order, how many swaps does bubble sort perform?

    • 4950
    • 99
    • 100
    • 9900

16. What is the worst-case time complexity of bubble sort?

    • O(n log n)
    • O(n)
    • O(log n)
    • O(n^2)

17. What should a stable bubble sort do when comparing two equal adjacent values?

    • Do not swap
    • Move to end
    • Swap them
    • Delete one

18. Bubble sort is applied to [3, 7, 2]. What is the list after the first pass?

    • [2, 3, 7]
    • [3, 7, 2]
    • [3, 2, 7]
    • [7, 3, 2]

19. Roughly how many comparisons does a worst-case bubble sort of 1024 items make?

    • 1,048,576
    • 523,776
    • 10,240
    • 1,023

20. A bubble sort is applied to a list that is already sorted, without the early-exit optimisation. How many swaps occur?

    • 0
    • n - 1
    • 1
    • n(n - 1) / 2

Related quizzes

• Breadth-first and depth-first search Quiz · 4.3.1.1 · 20 questions
• Pre-order, post-order and in-order traversal Quiz · 4.3.2.1 · 20 questions
• Infix to Reverse Polish notation Quiz · 4.3.3.1 · 20 questions
• Linear and binary search Quiz · 4.3.4.1 · 20 questions
• Binary tree search Quiz · 4.3.4.3 · 20 questions
• Merge sort Quiz · 4.3.5.2 · 20 questions
• Dijkstra's shortest path algorithm Quiz · 4.3.6.1 · 20 questions
• Data types Quiz · 4.1.1.1 · 20 questions
• Entity relationship modelling Quiz · 4.10.1.1 · 20 questions
• Big Data Quiz · 4.11.1.1 · 20 questions