Show the list [5, 2, 4, 1] after one pass of bubble sort.
- 5 > 2: swap → [2, 5, 4, 1].
- 5 > 4: swap → [2, 4, 5, 1].
- 5 > 1: swap → [2, 4, 1, 5].
Answer [2, 4, 1, 5]
A-level Computer Science revision · Data structures and algorithms
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.
Watch out Bubble sort can stop early if a pass makes no swaps.
Show the list [5, 2, 4, 1] after one pass of bubble sort.
Answer [2, 4, 1, 5]
How many comparisons does the first pass of bubble sort make on a list of 8 items?
What is the worst-case time complexity of insertion sort?
Insertion sort is applied to [3, 1, 2]. What is the list after the first item (1) is inserted?
A-level Computer Science Pro, OCR H446
£119 once
Price rises to £199 on 1 January. Save £80 by joining before then.
At least 12 months of access
No VAT is charged.