SLIDE 1
CSZone.co.uk
Click to reveal · Arrow keys also work
OCR J277 · Component 2 · Topic 2.1.3c

Sorting Algorithms
Bubble Sort

Compare · Swap · Repeat · Optimise

CSZone OCR GCSE Computer Science J277
Learning Objectives

By the end of this video you will be able to...

Describe how bubble sort works in plain English — including what is compared at each step, when a swap occurs, and how each pass places one more element in its final position
Write and identify bubble sort pseudocode — recognise its structure from the nested loop, adjacent comparison data[j] > data[j+1], and three-line swap using a TEMP variable
Apply bubble sort to a data set — show each comparison and swap across multiple passes until the list is fully sorted
Complete and interpret trace tables for bubble sort — tracking the state of the array after each pass, the number of swaps, and when the sort terminates
Explain the optimised version using a swapped flag — state efficiency (best, average, worst case) and compare bubble sort with linear and binary search
⚡ Bubble sort is the most frequently applied sorting algorithm in OCR J277 exam questions. Expect a step-by-step trace on almost every Component 2 paper.
Bubble Sort — The Concept

What is bubble sort?

DEFINITION
Bubble sort works by repeatedly comparing adjacent pairs of elements and swapping them if they are in the wrong order. After each full pass through the list, the largest unsorted element has "bubbled up" to its correct position at the end.
NO PREREQUISITE
Unlike binary search, bubble sort works on any data — sorted, unsorted, or partially sorted. No pre-processing needed.
THE PROCESS IN PLAIN ENGLISH
1.
Start at the beginning of the list.
2.
Compare the first pair of adjacent elements.
3.
If they are in the wrong order, swap them.
4.
Move to the next pair. Repeat steps 2–3.
5.
When you reach the end — that's one pass complete. The largest element is now in its final position.
6.
Repeat from step 1 for the remaining unsorted elements. Stop after n−1 passes.
WHY "BUBBLE" SORT?
Large elements gradually "bubble up" to the top (end) of the list with each pass — like air bubbles rising to the surface of water. After pass 1, the largest element is at the end. After pass 2, the second-largest is in its position. And so on.
WHAT EACH PASS GUARANTEES
After pass 1 → last element is sorted
After pass 2 → last 2 elements are sorted
After pass 3 → last 3 elements are sorted
After n−1 passes → entire list is sorted
This means each pass can do one fewer comparison than the last — we know the elements at the end are already in place.
⚡ A common exam question: "After how many passes is the list guaranteed to be sorted?" Answer: n−1 passes for a list of n elements. For a list of 5 elements, at most 4 passes are needed.
The Algorithm

Bubble sort — the nested loop structure

OUTER LOOP — PASSES
FOR i = 0 TO LEN(data) - 2
The outer loop controls how many passes we make. For a list of n elements, we need at most n−1 passes. i starts at 0; when i equals LEN−2 that's n−1 passes total.
INNER LOOP — COMPARISONS
FOR j = 0 TO LEN(data) - 2 - i
The inner loop compares adjacent pairs. The upper bound reduces by i each time — because after pass i, the last i elements are already in place and don't need comparing again.
THE SWAP MECHANISM
IF data[j] > data[j+1] THEN
temp = data[j]
data[j] = data[j+1]
data[j+1] = temp
END IF
Three lines to swap. TEMP holds the first value while it gets overwritten. Without TEMP, you'd lose the original value of data[j].
WHY THREE LINES TO SWAP?
You cannot swap two variables with two lines. If you wrote data[j] = data[j+1] first, you'd overwrite data[j] and lose it forever. The TEMP variable preserves the original value:
// Swap data[j]=8 and data[j+1]=3
temp = data[j] // temp = 8
data[j] = data[j+1] // data[j] = 3
data[j+1] = temp // data[j+1] = 8
The TEMP swap pattern is a key identifier of bubble sort. If you see it in an exam question alongside a nested loop and adjacent comparison, the algorithm is bubble sort.
⚡ After n−1 passes, the entire list is sorted — even if some passes made no swaps. The inner loop upper bound reduces by 1 each pass because the last i elements are already in their final positions after pass i.
Pseudocode

Bubble sort in pseudocode

BASIC VERSION
// Sort data[] into ascending order FOR i = 0 TO LEN(data) - 2 FOR j = 0 TO LEN(data) - 2 - i IF data[j] > data[j+1] THEN temp = data[j] data[j] = data[j+1] data[j+1] = temp END IF END FOR END FOR
⚡ You don't need to memorise this — but you must identify it. The three signatures: nested FOR loops, adjacent comparison data[j] > data[j+1], and the three-line TEMP swap. All three together = bubble sort.
ANATOMY — KEY LINES EXPLAINED
FOR i = 0 TO LEN-2 — outer loop. Runs n−1 times; each pass guarantees one more element is in place.
FOR j = 0 TO LEN-2-i — inner loop. The -i means each pass does one fewer comparison (last i elements already sorted).
data[j] > data[j+1] — adjacent comparison. j+1 is the key — it's always the next element, not some fixed index.
temp / data[j] / data[j+1] — three-line swap. The order matters: save → overwrite → restore from TEMP.
DESCENDING ORDER
To sort in descending order, change data[j] > data[j+1] to data[j] < data[j+1]. Everything else stays the same. The comparison direction is the only change.
Applying Bubble Sort

Applying it — Pass 1 in full

LIST: [4, 2, 7, 1, 5]  ·  5 elements  ·  PASS 1: 4 comparisons
■ comparing■ swapped■ placed
STEP 1
4
2
7
1
5
0
1
2
3
4
4 > 2 → SWAP
2
4
7
1
5
STEP 2
2
4
7
1
5
4 < 7 → no swap
STEP 3
2
4
7
1
5
7 > 1 → SWAP
2
4
1
7
5
STEP 4
2
4
1
7
5
7 > 5 → SWAP
2
4
1
5
7
PASS 1 COMPLETE
2
4
1
5
7
Result: [2, 4, 1, 5, 7]
Swaps made this pass: 3
Largest element 7 has bubbled to index 4 — it's now in its final position. We can ignore it in future passes.
⚡ After each pass, the last i elements are guaranteed to be in their final positions. Pass 2 only needs to compare 3 pairs (not 4). This is why the inner loop uses LEN-2-i as its upper bound.
Applying Bubble Sort

Passes 2, 3 and the completion check

AFTER PASS 1: [2, 4, 1, 5, 7] — continuing with first 4 elements
PASS 2 — 3 COMPARISONS
STEP 1
2
4
1
5
7
2 < 4 → no swap
STEP 2
2
4
1
5
7
4 > 1 → SWAP
2
1
4
5
7
STEP 3
2
1
4
5
7
4 < 5 → no swap
After pass 2: [2, 1, 4, 5, 7]  ·  1 swap  ·  5 placed at index 3
PASS 3 — 2 COMPARISONS
STEP 1
2
1
4
5
7
2 > 1 → SWAP
1
2
4
5
7
STEP 2
1
2
4
5
7
2 < 4 → no swap
After pass 3: [1, 2, 4, 5, 7]  ·  1 swap  ·  List is now sorted!
PASS 4 — OPTIMISATION CHECK
STEP 1
1
2
4
5
7
1 < 2 → no swap
Pass 4: 0 swaps. Optimised version detects swapped=FALSE → stops immediately.
1
2
4
5
7
FULLY SORTED: [1, 2, 4, 5, 7] ✓
Basic version: would have run pass 4 regardless. Optimised version: exit after pass 3 if no swaps occurred — but since pass 3 DID swap, we check pass 4. Pass 4 has no swaps → stop.
⚡ Summary: [4,2,7,1,5] sorted in passes: Pass 1 → 3 swaps. Pass 2 → 1 swap. Pass 3 → 1 swap. Pass 4 → 0 swaps (stop). Total swaps: 5. Total comparisons: 4+3+2+1 = 10.
Trace Table

Trace table — bubble sort on [4, 2, 7, 1, 5]

ALGORITHM BEING TRACED
data = [4, 2, 7, 1, 5] FOR i = 0 TO LEN(data) - 2 FOR j = 0 TO LEN(data) - 2 - i IF data[j] > data[j+1] THEN temp = data[j] data[j] = data[j+1] data[j+1] = temp END IF END FOR END FOR
Yellow = changed  ·  Green = final sorted array
TRACE TABLE — STATE AFTER EACH PASS
Pass (i)Array after passSwapsElement placed
—[4, 2, 7, 1, 5]—Initial state
0[2, 4, 1, 5, 7]37 → index 4
1[2, 1, 4, 5, 7]15 → index 3
2[1, 2, 4, 5, 7]14 → index 2
3[1, 2, 4, 5, 7]0SORTED ✓
Pass 4 (i=3) does 1 comparison and 0 swaps. With the optimised version, this is where swapped=FALSE triggers the early exit. Without optimisation, this pass still runs.
⚡ Exam: "How many passes were needed?" → 4 (basic) or 3 useful passes + 1 check (optimised). "How many comparisons in pass 2?" → LEN−2−1 = 3. "What is the array after pass 1?" → [2,4,1,5,7].
Optimisation

The optimised version — swapped flag

THE PROBLEM WITH BASIC BUBBLE SORT
The basic version always performs n−1 full passes — even if the list becomes sorted after pass 1. For an almost-sorted list, this wastes comparisons. The optimised version adds a swapped flag that stops the sort as soon as a pass makes no swaps.
THE KEY INSIGHT
If a full pass makes zero swaps, the list is already in order — no element needed to move. There is no point continuing. The swapped flag detects this condition and exits the loop early.
OPTIMISED PSEUDOCODE
swapped = TRUE i = 0 WHILE swapped == TRUE swapped = FALSE ← reset before each pass FOR j = 0 TO LEN(data) - 2 - i IF data[j] > data[j+1] THEN temp = data[j] data[j] = data[j+1] data[j+1] = temp swapped = TRUE ← set if any swap occurs END IF END FOR i = i + 1 END WHILE
HOW THE FLAG WORKS
swapped = TRUE at the start — ensures the WHILE loop runs at least once.
swapped = FALSE at the start of each pass — assume this pass will make no swaps.
swapped = TRUE inside the IF — if ANY swap happens, set the flag back to TRUE.
After the inner loop: if swapped is still FALSE, no swap occurred → list is sorted → WHILE exits.
BEST CASE WITH OPTIMISATION
If the list is already sorted, the first pass makes zero swaps. swapped stays FALSE. The WHILE exits after just one pass — making n−1 comparisons but no swaps. This is the best case: O(n).
⚡ Exam: "Describe one improvement that can be made to the basic bubble sort algorithm." Answer: add a swapped flag that is set to FALSE at the start of each pass and TRUE whenever a swap occurs. If the flag is still FALSE after a complete pass, the list is sorted and the algorithm stops early.
Efficiency

Efficiency — bubble sort

BUBBLE SORT EFFICIENCY
BEST
O(n)
With optimisation only. List is already sorted — first pass makes zero swaps, flag triggers early exit. n−1 comparisons, zero swaps.
AVERAGE
O(n²)
Approximately n²/4 comparisons and swaps. Data is in random order. Multiple passes needed, each making some swaps.
WORST
O(n²)
List is in reverse order. Every comparison causes a swap. n(n−1)/2 total comparisons. For 5 elements: 4+3+2+1 = 10 comparisons.
⚡ Worst case: n(n−1)/2 comparisons. For 5 elements: 10. For 10 elements: 45. For 100: 4,950. Bubble sort gets very slow on large lists — it is one of the least efficient sorting algorithms.
COMPARISON: BUBBLE vs LINEAR vs BINARY
LINEAR
SEARCH		BINARY
SEARCH		BUBBLE
SORT
TypeSearchSearchSort
Needs sorted?NoYesNo
Best caseO(1)O(1)O(n)*
Worst caseO(n)O(log n)O(n²)
Large dataSlowFastVery slow
* Best case O(n) only with the swapped flag optimisation
Use bubble sort when data is small or nearly sorted (with optimisation).
Avoid bubble sort for large datasets — it is O(n²) on average, far worse than binary search for data already sorted.
⚡ "Give one disadvantage of bubble sort." Answer: it has O(n²) worst-case efficiency, making it very slow for large datasets compared to more efficient algorithms like merge sort.
Exam Practice

Bubble sort — applying the algorithm

Question 1 — 4 marks
Perform one complete pass of bubble sort on the list below, showing each comparison and swap. State the result after the pass.

List: [9, 3, 7, 1, 6]
Answer — Q1
Compare (9,3): 9>3 → swap → [3,9,7,1,6]
Compare (9,7): 9>7 → swap → [3,7,9,1,6]
Compare (9,1): 9>1 → swap → [3,7,1,9,6]
Compare (9,6): 9>6 → swap → [3,7,1,6,9]
After pass 1: [3, 7, 1, 6, 9] — 4 swaps — 9 placed.
Question 2 — 3 marks
Using the same original list [9, 3, 7, 1, 6], show the complete trace of bubble sort — state the array after every pass until it is fully sorted.
Answer — Q2
Pass 1: [3, 7, 1, 6, 9] — 4 swaps
Pass 2: [3, 1, 6, 7, 9] — 2 swaps
Pass 3: [1, 3, 6, 7, 9] — 1 swap
Pass 4: [1, 3, 6, 7, 9] — 0 swaps → SORTED
Question 3 — 4 marks
The algorithm below is used to sort an array.
(a) What type of sort does this code show?
(b) Identify two features that led to your answer.
(c) Describe one improvement that could be made to this algorithm and explain the benefit.
FOR x = 0 TO LEN(arr) - 2 FOR y = 0 TO LEN(arr) - 2 - x IF arr[y] > arr[y+1] THEN hold = arr[y] arr[y] = arr[y+1] arr[y+1] = hold END IF END FOR END FOR
Exam Practice — Answers

Question 3 answered + common mistakes

Q3 ANSWER
(a) Bubble sort (1 mark)
(b) Any two from: nested FOR loops / adjacent comparison arr[y] > arr[y+1] (using y+1 not a fixed index) / three-line swap using a temporary variable (hold) / inner loop upper bound reduces by x each pass (1 mark each, max 2 marks)
(c) Add a swapped flag — set it to FALSE at the start of each pass and TRUE whenever a swap occurs. If the flag is FALSE after a complete pass, the list is sorted and the sort stops early. Benefit: reduces unnecessary comparisons on nearly-sorted or already-sorted data (1 mark)
IDENTIFICATION — WHAT MAKES BUBBLE SORT UNIQUE
The three signatures: (1) nested loops — outer controls passes, inner controls comparisons. (2) Adjacent comparison using data[j] and data[j+1] — j+1 is always j's neighbour. (3) Three-line TEMP swap. All three together = bubble sort, regardless of variable names.
COMMON MISTAKES
1
Trying to swap with two lines instead of three. You need the TEMP variable. Writing data[j] = data[j+1] first overwrites and loses data[j].
2
Forgetting the inner loop reduces each pass. In pass 2, you compare 3 pairs, not 4. Checking already-placed elements wastes time and may confuse your trace.
3
Stopping too early. One pass with no swaps means sorted — but only if you completed a full pass. Stopping mid-pass because you "see" it's sorted is wrong.
4
Confusing passes with comparisons. A pass is one full run of the inner loop. A comparison is one adjacent pair check. For 5 elements, pass 1 has 4 comparisons.
⚡ In a trace table, show the state of the array AFTER each complete pass, not after each comparison — unless the question specifically asks for every step. Read the question carefully.
Advantages & Disadvantages

Bubble sort — strengths and weaknesses

✓ ADVANTAGES
Simple to understand and implement — straightforward nested loops and an easy-to-follow swap. One of the simplest sorting algorithms to write from memory.
Works on any data — no prerequisite of sorted data. Can sort ascending or descending simply by changing the comparison operator.
Efficient on nearly-sorted data (with swapped flag) — best case O(n). If data is already sorted, just one pass confirms it.
⚡ "Give one advantage of bubble sort." Answer: it is simple to implement — the nested loops and adjacent swap are easy to understand and code correctly.
✗ DISADVANTAGES
Very slow on large datasets — O(n²) average and worst case. For 1,000 elements, up to 500,000 comparisons. Merge sort would need only ~10,000.
One of the least efficient sorting algorithms — in practice, merge sort and insertion sort significantly outperform bubble sort for real-world data.
Many passes required in worst case — a reverse-sorted list of n elements needs n−1 passes and n(n−1)/2 comparisons, all resulting in swaps.
⚡ "Give one disadvantage of bubble sort." Answer: it has O(n²) worst-case efficiency — it becomes very slow for large datasets because the number of comparisons grows proportionally to the square of the number of elements.
Summary

2.1.3c — Bubble Sort

HOW IT WORKS
Repeatedly compare adjacent pairs. Swap if in wrong order. After each pass, the largest unsorted element is in its final position. Repeat for n−1 passes.
IDENTIFYING FROM CODE — 3 SIGNATURES
(1) Nested loops. (2) Adjacent comparison: data[j] > data[j+1]. (3) Three-line TEMP swap. All three = bubble sort.
OPTIMISATION — SWAPPED FLAG
Set swapped=FALSE before each pass; set TRUE on any swap. If FALSE after full pass → list sorted → stop early. Improves best case to O(n).
EFFICIENCY
Best (with opt.): O(n) — already sorted, 1 pass. Average: O(n²). Worst (reverse sorted): O(n²) — n(n−1)/2 comparisons. Slow on large data.
VS OTHER ALGORITHMS
Advantage: simpler to implement than merge sort or insertion sort. Disadvantage: much slower on large data. No prerequisite needed (unlike binary search). Next up: merge sort — significantly more efficient but more complex.
2.1.3c Complete

That's Bubble Sort done!

Next up: 2.1.3d — Merge Sort

📝
MARKED WORKSHEET
CSZone.co.uk
🎯
QUIZ
CSZone.co.uk
📊
SLIDES
CSZone.co.uk