A-Level Computer Science / Unit 10: Organising Data in Programs

10.2.4 Ordering Values with Bubble Sort

🔒 Lesson slides are available to signed-in users. Sign in

10.2.4 Ordering Values with Bubble Sort

Bubble sort orders the values in a one-dimensional array by comparing neighbouring elements. When a pair is in the wrong order, the algorithm swaps the two values. Repeated passes gradually move values into their final positions.

By the end of this section, you should be able to:

  • Explain how adjacent comparisons and swaps produce an ordered array.
  • Trace the state of an array after individual comparisons and complete passes.
  • Write pseudocode that sorts a 1D array into ascending order.
  • Use a temporary variable to swap two array elements safely.
  • Explain why the unsorted range becomes shorter after each pass.
  • Use a Boolean flag to stop early when a pass makes no swaps.
  • Adapt the comparison condition to produce descending order.

The Main Idea

A delivery company stores six route durations, in minutes, using indexes 3 to 8. The values need to be arranged from shortest to longest.

Index 3 4 5 6 7 8
RouteDuration 42 17 29 11 35 24

For ascending order, compare each adjacent pair. Swap the pair whenever the value on the left is greater than the value on the right.

Bubble sort: a sorting algorithm that repeatedly compares adjacent elements and swaps pairs that are in the wrong order.
Exam tip: Bubble sort compares neighbours. A method that searches for the smallest value and moves it directly is a different sorting algorithm.

Tracing One Complete Pass

During the first pass, the comparison moves from the lower bound towards the upper bound. The table shows the array after each decision.

Comparison Pair checked Decision Array after the decision
1 42 and 17 Swap 17, 42, 29, 11, 35, 24
2 42 and 29 Swap 17, 29, 42, 11, 35, 24
3 42 and 11 Swap 17, 29, 11, 42, 35, 24
4 42 and 35 Swap 17, 29, 11, 35, 42, 24
5 42 and 24 Swap 17, 29, 11, 35, 24, 42
After the first pass, the largest value in the current unsorted region, 42, has reached the upper-bound position. The other values are not necessarily sorted yet.
Common mistake: One pass does not normally sort the complete array. It guarantees only that one extreme value has reached the end of the current unsorted region.

Swapping Two Array Elements

Assigning the right value directly to the left element would overwrite data that is still needed. A temporary variable protects the first value while the swap takes place. 

Temporary ← RouteDuration[Index]
RouteDuration[Index] ← RouteDuration[Index + 1]
RouteDuration[Index + 1] ← Temporary
Stage Left element Right element Temporary
Before the swap 42 17 Not set
Save the left value 42 17 42
Copy right to left 17 17 42
Restore the saved value 17 42 42
Common mistake: These two statements do not perform a valid swap: 
RouteDuration[Index] ← RouteDuration[Index + 1]
RouteDuration[Index + 1] ← RouteDuration[Index]
The original left value has already been lost before the second statement runs.

Repeated Passes and the Shrinking Range

Each completed pass places the largest remaining unsorted value at the end of the unsorted region. The next pass can therefore stop one position earlier.

Stage Array state Newly fixed value
Initial 42, 17, 29, 11, 35, 24 None
After pass 1 17, 29, 11, 35, 24, 42 42
After pass 2 17, 11, 29, 24, 35, 42 35
After pass 3 11, 17, 24, 29, 35, 42 29
Pass 4 11, 17, 24, 29, 35, 42 No swaps: the array is already sorted
Pass: one movement through the current unsorted region, comparing each adjacent pair once.
When tracing, clearly separate an individual comparison from a complete pass. They are not the same event.

Bubble Sort Pseudocode

This version works with a non-zero lower bound and uses LastUnsorted to mark the final position that still needs comparing. 

DECLARE RouteDuration : ARRAY[3:8] OF INTEGER
DECLARE LowerBound : INTEGER
DECLARE UpperBound : INTEGER
DECLARE LastUnsorted : INTEGER
DECLARE Index : INTEGER
DECLARE Temporary : INTEGER
DECLARE SwapMade : BOOLEAN

LowerBound ← 3
UpperBound ← 8
LastUnsorted ← UpperBound

REPEAT
    SwapMade ← FALSE

    FOR Index ← LowerBound TO LastUnsorted - 1
        IF RouteDuration[Index] > RouteDuration[Index + 1]
          THEN
            Temporary ← RouteDuration[Index]
            RouteDuration[Index] ← RouteDuration[Index + 1]
            RouteDuration[Index + 1] ← Temporary
            SwapMade ← TRUE
        ENDIF
    NEXT Index

    LastUnsorted ← LastUnsorted - 1
UNTIL SwapMade = FALSE OR LastUnsorted = LowerBound

Purpose of the main identifiers

Identifier Purpose
Index Selects the left element of the adjacent pair.
Index + 1 Selects the right-hand neighbour.
Temporary Protects one value during a swap.
LastUnsorted Shortens the comparison range after each pass.
SwapMade Records whether the current pass changed the array.
The inner loop stops at LastUnsorted - 1 because it also accesses Index + 1. Allowing Index to equal LastUnsorted would read beyond the current comparison range.

Stopping Early When No Swaps Occur

At the start of each pass, SwapMade is reset to FALSE. Any swap changes it to TRUE. If the complete pass finishes and it is still FALSE, every adjacent pair was already in the required order.

Array before the pass Swaps in the pass Conclusion
8, 13, 17, 19, 26, 31 0 Already sorted; stop immediately.
8, 13, 19, 17, 26, 31 1 A change occurred; another pass is needed to confirm the order.
Do not initialise SwapMade only once before all passes. It must be reset at the beginning of every new pass so that the algorithm measures changes in that pass alone.

Adapting the Sort for Descending Order

The loop structure and swap statements stay the same. Only the comparison condition changes.

Required order Swap condition Effect
Ascending Array[Index] > Array[Index + 1] Larger values move towards the upper bound.
Descending Array[Index] < Array[Index + 1] Smaller values move towards the upper bound.
Common mistake: Do not reverse the swap statements. Change the condition that decides whether the pair is in the wrong order.

Interactive: Bubble Sort Animator

Select a data set and sorting direction. Step through one adjacent comparison at a time, complete a whole pass, or let the animation run automatically. The widget also shows the shrinking unsorted range.

Pass 1
Comparisons 0
Swaps 0
Last unsorted index 8
Current operation

Ready to compare the first adjacent pair.

IF RouteDuration[3] > RouteDuration[4]

Compare 42 with 17.

Common Mistakes and Misconceptions

  • Comparing non-adjacent elements instead of neighbours.
  • Assuming one pass completely sorts the array.
  • Overwriting one value because no temporary variable is used.
  • Using an inner-loop upper limit that makes Index + 1 invalid.
  • Continuing to compare the values already fixed at the upper end.
  • Forgetting to reset the swap flag before each pass.
  • Stopping after a pass that did make a swap.
  • Changing the swap statements instead of the comparison when descending order is required.
  • Ignoring the declared lower bound and assuming the first index is 0.

Practice

Task 1: Trace a complete first pass

QueueTime : ARRAY[5:10] OF INTEGER contains:

31, 14, 26, 9, 22, 18

  1. Show the array after each adjacent comparison in the first ascending pass.
  2. State which value reaches its final position.
  3. State the last index that needs checking in pass 2.

Task 2: Complete the swap

Complete the missing pseudocode:

IF Score[Index] > Score[Index + 1]
  THEN
    Temporary ← ____________________
    Score[Index] ← ____________________
    Score[Index + 1] ← ____________________
    SwapMade ← TRUE
ENDIF

Task 3: Write and adapt an algorithm

  1. Write bubble-sort pseudocode for ARRAY[2:9] OF INTEGER.
  2. Use a shrinking unsorted boundary.
  3. Add early termination using a Boolean flag.
  4. State the one comparison change needed for descending order.

Review

Question Strong answer should include
What does bubble sort compare? Adjacent elements in the current unsorted region.
When is a pair swapped for ascending order? When the left value is greater than the right value.
Why is a temporary variable used? To preserve one value while the two array elements exchange positions.
What is guaranteed after one pass? The largest value in the unsorted region reaches its final upper-end position.
Why can the range shrink? Values already fixed at the end do not need comparing again.
When can the algorithm stop early? When a complete pass finishes without any swaps.
Final exam tip: Test your pseudocode with an already sorted array, a reverse-ordered array and a two-element array. These cases reveal incorrect loop limits and swap-flag logic quickly.