Pseudocode Hub - Master CIE IGCSE & AS Level Pseudocode

23.1 What is Bubble Sort?

Bubble sort is a simple sorting algorithm that repeatedly compares adjacent elements.
If two adjacent elements are in the wrong order, they are swapped.
Each “pass” moves the largest unsorted element to its correct position — it “bubbles” to the end.
After n - 1 passes, an array of n elements is fully sorted.
Simple to understand but inefficient for large arrays (O(n²) time complexity).

Key idea: The name “bubble” comes from the way larger values bubble up towards the end of the array with each pass — like air bubbles rising in water. After pass I, the last I elements are in their final positions.

Common mistake: Bubble sort is not the same as linear search. Linear search finds a value in an array; bubble sort arranges values into order. Searching vs sorting — different jobs.

Knowledge Check 1

What is Bubble Sort?

23.2 The Bubble Sort Algorithm

Step 1: Start at the beginning of the array (index 1).
Step 2: Compare the first two adjacent elements.
Step 3: If the first is greater than the second, SWAP them.
Step 4: Move to the next pair and repeat.
Step 5: After one complete pass, the largest element is at the end.
Step 6: Repeat passes for the remaining unsorted elements.

Example: input 5 numbers and sort them in ascending order

DECLARE Numbers : ARRAY[1:5] OF INTEGER
DECLARE I, J : INTEGER
DECLARE Temp : INTEGER
FOR I <- 1 TO 5
  OUTPUT "Enter number: "
  INPUT Numbers[I]
NEXT I
FOR I <- 1 TO 4
  FOR J <- 1 TO 5 - I
    IF Numbers[J] > Numbers[J + 1] THEN
      Temp <- Numbers[J]
      Numbers[J] <- Numbers[J + 1]
      Numbers[J + 1] <- Temp
    ENDIF
  NEXT J
NEXT I
OUTPUT "Sorted array:"
FOR I <- 1 TO 5
  OUTPUT Numbers[I]
NEXT I

Exam tip: The outer loop runs FOR I <- 1 TO n - 1 (n−1 passes) and the inner loop runs FOR J <- 1 TO n - I. The - I part is what makes the inner loop shrink each pass — the last I elements are already sorted, so they are skipped.

Knowledge Check 2

The Bubble Sort Algorithm

23.3 How Swapping Works

Swapping requires a TEMPORARY variable (Temp).
Three steps to swap A and B:
1. Temp <- A (save A's value)
2. A <- B (copy B into A)
3. B <- Temp (copy saved A into B)
WITHOUT Temp: A <- B then B <- A would lose A's original value.

Example: swap Numbers[2] and Numbers[3]

Temp <- Numbers[2]
Numbers[2] <- Numbers[3]
Numbers[3] <- Temp

Correct — uses Temp

Temp <- A
A <- B
B <- Temp
// A and B are now swapped

Incorrect — no Temp

A <- B
B <- A
// Both A and B now equal
// B's original value!

Key idea: The Temp variable acts as a “safe box” — it stores one value before that variable is overwritten, so the saved value can be restored into the other variable at the end. Without the safe box, the original value is lost forever.

Knowledge Check 3

How Swapping Works

23.4 Tracing a Bubble Sort

A trace table records each comparison and swap step by step.
Typical columns: Pass (I), J, Comparison, Action, Array state.
Each row = one J iteration inside a pass.
The trace ends when the outer loop finishes all n - 1 passes.

Example: sort [5, 3, 8, 1] in ascending order

Pass (I)	J	Comparison	Action	Array state
1	1	5 > 3 ?	Yes — swap	[3, 5, 8, 1]
1	2	5 > 8 ?	No	[3, 5, 8, 1]
1	3	8 > 1 ?	Yes — swap	[3, 5, 1, 8]
2	1	3 > 5 ?	No	[3, 5, 1, 8]
2	2	5 > 1 ?	Yes — swap	[3, 1, 5, 8]
3	1	3 > 1 ?	Yes — swap	[1, 3, 5, 8]

Sorted result: [1, 3, 5, 8] after 3 passes (n − 1 = 4 − 1 = 3) and 6 comparisons (3 + 2 + 1).

Common mistake: After a swap, both the array state changes. Make sure to record the array after the swap, not before — and remember that comparisons where no swap happens (e.g. 5 > 8? → No) still count as a row in the trace table.

Knowledge Check 4

Tracing a Bubble Sort

23.5 Optimisation and Variations

Early exit optimisation: if no swaps happen during a pass, the array is already sorted.
Use a BOOLEAN flag (Swapped) to track whether any swaps occurred.
If Swapped is still FALSE after a pass, stop early.
Descending order: change the comparison from > to <.

Example: optimised bubble sort with early-exit flag

DECLARE Swapped : BOOLEAN
FOR I <- 1 TO 4
  Swapped <- FALSE
  FOR J <- 1 TO 5 - I
    IF Numbers[J] > Numbers[J + 1] THEN
      Temp <- Numbers[J]
      Numbers[J] <- Numbers[J + 1]
      Numbers[J + 1] <- Temp
      Swapped <- TRUE
    ENDIF
  NEXT J
  IF NOT Swapped THEN
    I <- 5  // force exit
  ENDIF
NEXT I

Exam tip: The optimised version has a best case of O(n) (array already sorted — one pass, no swaps, exit). The unoptimised version is always O(n²) because it runs every pass regardless. For descending order, change Numbers[J] > Numbers[J + 1] to Numbers[J] < Numbers[J + 1].

Knowledge Check 5

Optimisation and Variations

23.6 Key Points Summary

Bubble sort compares adjacent elements and swaps them if out of order.

Each pass moves the largest unsorted element to the end.

Needs (n - 1) passes for n elements (outer loop: FOR I <- 1 TO n - 1).

Swapping requires a Temp variable (3 steps).

Inner loop range shrinks each pass: FOR J <- 1 TO n - I.

Can be optimised with a Swapped (BOOLEAN) flag for early exit.

Change > to < for descending order.

Time complexity: O(n²) worst case — not efficient for large arrays.

Optimised version best case: O(n) when array is already sorted.

Bubble sort is an AS Level topic.

Exam tip: Whenever an exam question says “sort this array” or “arrange in ascending order”, reach for bubble sort with nested FOR loops and the 3-step swap. If the question asks for efficiency, mention the Swapped flag for early exit — it turns the best case into O(n).

Knowledge Check 6

Bubble Sort