A-level Computer Science revision · Data structures and algorithms

Bubble sort and insertion sort

The idea

Bubble sort repeatedly passes through a list, swapping adjacent items in the wrong order, until a pass makes no swaps. Insertion sort builds a sorted section one item at a time, inserting each new item into its correct place. Both are O(n²) in the worst case but simple and good for small or nearly sorted lists.

  1. Bubble: compare neighbours, swap, repeat passes.
  2. Insertion: take next item, shift larger items right, insert.
  3. Both O(n²) worst case; insertion sort is O(n) on sorted data.

Watch out Bubble sort can stop early if a pass makes no swaps.

See it worked

Worked example

Show the list [5, 2, 4, 1] after one pass of bubble sort.

  1. 5 > 2: swap → [2, 5, 4, 1].
  2. 5 > 4: swap → [2, 4, 5, 1].
  3. 5 > 1: swap → [2, 4, 1, 5].

Answer [2, 4, 1, 5]

Your turn

Question 12 marks

How many comparisons does the first pass of bubble sort make on a list of 8 items?

Question 21 mark

What is the worst-case time complexity of insertion sort?

Choose one
Question 31 mark

Insertion sort is applied to [3, 1, 2]. What is the list after the first item (1) is inserted?

Choose one

A-level Computer Science Pro, OCR H446

A-level Computer Science Pro

£119 once

Price rises to £199 on 1 January. Save £80 by joining before then.

At least 12 months of access

By paying you agree to our Terms and get access straight away, which ends your 14-day cancellation right.

No VAT is charged.

Independent practice for OCR A-level Computer Science (H446), not endorsed by OCR.

Privacy · Terms