Bubble Sort Algorithm

This lesson covers the bubble sort algorithm as required by OCR J277 Section 2.2. Bubble sort is one of the three standard sorting algorithms you must know for the OCR GCSE Computer Science exam. You need to understand how it works, be able to write it in pseudocode, trace through it, and evaluate its efficiency.

---

What Is Bubble Sort?

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent (neighbouring) elements, and swaps them if they are in the wrong order. This process is repeated until no more swaps are needed, meaning the list is sorted.

The algorithm gets its name because smaller values gradually "bubble" to the top (front) of the list while larger values sink to the bottom (end), like bubbles rising in water.

---

How Bubble Sort Works

1. Start at the first element of the list.
2. Compare the current element with the next element.
3. If the current element is greater than the next element, swap them.
4. Move to the next pair of adjacent elements and repeat the comparison.
5. After one complete pass through the list, the largest unsorted value is now in its correct position at the end.
6. Repeat the process for the remaining unsorted portion of the list.
7. Continue until a complete pass is made with no swaps — the list is now sorted.

The following flowchart shows the bubble sort comparison and swap process:

flowchart TD
    A([Start]) --> B["Set swapped = true"]
    B --> C{swapped = true?}
    C -- No --> Z(["List is sorted\nEnd"])
    C -- Yes --> D["Set swapped = false\nStart at first pair"]
    D --> E{"Current >\nNext?"}
    E -- Yes --> F["Swap the\ntwo elements"]
    F --> G["Set swapped = true"]
    G --> H{More pairs?}
    E -- No --> H
    H -- Yes --> I["Move to next pair"]
    I --> E
    H -- No --> C

---

Bubble Sort in OCR Pseudocode

procedure bubbleSort(list)
    n = list.length
    swapped = true

    while swapped == true
        swapped = false
        for i = 0 to n - 2
            if list[i] > list[i + 1] then
                temp = list[i]
                list[i] = list[i + 1]
                list[i + 1] = temp
                swapped = true
            endif
        next i
        n = n - 1
    endwhile
endprocedure

Bubble Sort in Python

def bubble_sort(lst):
    n = len(lst)
    swapped = True

    while swapped:
        swapped = False
        for i in range(n - 1):
            if lst[i] > lst[i + 1]:
                lst[i], lst[i + 1] = lst[i + 1], lst[i]
                swapped = True
        n -= 1

    return lst

numbers = [5, 3, 8, 1, 2]
print(bubble_sort(numbers))  # Output: [1, 2, 3, 5, 8]

OCR Exam Tip: The optimised version reduces n by 1 after each pass because the last element is guaranteed to be in the correct position. Also, using a swapped flag to detect early completion is an important optimisation — mention it if asked about improving bubble sort.

---

Tracing Through Bubble Sort

Let us sort the list [5, 3, 8, 1, 2] using bubble sort:

Pass 1:

Comparison	List State	Swap?
5 > 3? Yes	[3, 5, 8, 1, 2]	Yes
5 > 8? No	[3, 5, 8, 1, 2]	No
8 > 1? Yes	[3, 5, 1, 8, 2]	Yes
8 > 2? Yes	[3, 5, 1, 2, 8]	Yes

After Pass 1: [3, 5, 1, 2, 8] — 8 is in its correct position.

Pass 2:

Comparison	List State	Swap?
3 > 5? No	[3, 5, 1, 2, 8]	No
5 > 1? Yes	[3, 1, 5, 2, 8]	Yes
5 > 2? Yes	[3, 1, 2, 5, 8]	Yes

After Pass 2: [3, 1, 2, 5, 8] — 5 is in its correct position.

Pass 3:

Comparison	List State	Swap?
3 > 1? Yes	[1, 3, 2, 5, 8]	Yes
3 > 2? Yes	[1, 2, 3, 5, 8]	Yes

After Pass 3: [1, 2, 3, 5, 8] — 3 is in its correct position.

Pass 4: No swaps needed — list is sorted.

---

Properties of Bubble Sort

Property	Detail
Best case	O(n) — already sorted, one pass with no swaps
Worst case	O(n²) — data is in reverse order
Average case	O(n²)
Space complexity	O(1) — sorts in place, no extra list needed
Stability	Stable — equal elements maintain their relative order
Adaptive	Yes — detects if already sorted (with swapped flag)

---

Summary

• Bubble sort compares adjacent elements and swaps them if in the wrong order.
• After each pass, the largest unsorted value "bubbles" to its correct position.
• It stops when a complete pass has no swaps.
• Best case is O(n) for already sorted data; worst case is O(n²).
• It sorts in place and is simple to implement, but inefficient for large datasets.

OCR Exam Tip: When asked to "show the state of the list after each pass", you must show the complete list after every full pass through the data — not after every individual swap. This is a common mistake that loses marks.

---

Extended Trace: Reverse-Sorted Data (Worst Case)

Let us sort [5, 4, 3, 2, 1] with bubble sort. This is the worst-case scenario for bubble sort because every pair must be swapped.

Pass 1:

Comparison	List State	Swap?
5 > 4? Yes	[4, 5, 3, 2, 1]	Yes
5 > 3? Yes	[4, 3, 5, 2, 1]	Yes
5 > 2? Yes	[4, 3, 2, 5, 1]	Yes
5 > 1? Yes	[4, 3, 2, 1, 5]	Yes

After Pass 1: [4, 3, 2, 1, 5].

Pass 2:

Comparison	List State	Swap?
4 > 3? Yes	[3, 4, 2, 1, 5]	Yes
4 > 2? Yes	[3, 2, 4, 1, 5]	Yes
4 > 1? Yes	[3, 2, 1, 4, 5]	Yes

After Pass 2: [3, 2, 1, 4, 5].

Pass 3: After swaps, list becomes [2, 1, 3, 4, 5]. Pass 4: After swaps, list becomes [1, 2, 3, 4, 5]. Pass 5: No swaps — sorted.

For n = 5 elements in reverse order, bubble sort needed 4 + 3 + 2 + 1 = 10 swaps and 5 full passes. This illustrates the O(n²) worst case.

---

Best-Case Trace: Already Sorted

Now let us sort the already-sorted list [1, 2, 3, 4, 5]:

Pass 1: