Bubble Sort

Bubble sort is one of the simplest sorting algorithms. It works by repeatedly stepping through the list, comparing adjacent (neighbouring) pairs of elements, and swapping them if they are in the wrong order. This process is repeated until the list is sorted.

The name "bubble sort" comes from the way the largest values "bubble up" to the end of the list with each pass.

---

How Bubble Sort Works

1. Start at the beginning of the list.
2. Compare the first two adjacent elements.
3. If the first element is greater than the second, swap them.
4. Move to the next pair of adjacent elements and repeat the comparison and swap.
5. Continue until you reach the end of the list — this completes one pass.
6. After each pass, the largest unsorted element is in its correct position at the end.
7. Repeat the passes until a complete pass is made with no swaps — the list is now sorted.

The pass-and-swap loop in flowchart form:

graph TD
    A["Start of pass: j = 0, swapped = FALSE"] --> B{"j less than n - 1 - i?"}
    B -->|No| C{"Any swaps this pass?"}
    B -->|Yes| D{"list[j] > list[j+1]?"}
    D -->|Yes| E["Swap list[j] and list[j+1], swapped = TRUE"]
    D -->|No| F["No swap"]
    E --> G["j = j + 1"]
    F --> G
    G --> B
    C -->|No| H["List is sorted — terminate"]
    C -->|Yes| I["Start next pass"]
    I --> A

---

Pseudocode for Bubble Sort

FUNCTION bubbleSort(list)
    n = LENGTH(list)
    FOR i = 0 TO n - 2
        swapped = FALSE
        FOR j = 0 TO n - 2 - i
            IF list[j] > list[j + 1] THEN
                SWAP list[j] AND list[j + 1]
                swapped = TRUE
            ENDIF
        NEXT j
        IF swapped = FALSE THEN
            RETURN list
        ENDIF
    NEXT i
    RETURN list
ENDFUNCTION

Note: The optimisation IF swapped = FALSE THEN RETURN allows the algorithm to stop early if the list is already sorted before all passes are completed.

---

Worked Example

Sort the list: [5, 3, 8, 1, 2]

Pass 1

Comparison	List Before	Swap?	List After
5 vs 3	[5, 3, 8, 1, 2]	Yes	[3, 5, 8, 1, 2]
5 vs 8	[3, 5, 8, 1, 2]	No	[3, 5, 8, 1, 2]
8 vs 1	[3, 5, 8, 1, 2]	Yes	[3, 5, 1, 8, 2]
8 vs 2	[3, 5, 1, 8, 2]	Yes	[3, 5, 1, 2, 8]

After Pass 1: [3, 5, 1, 2, 8] — the largest value (8) is now in its correct position.

Pass 2

Comparison	List Before	Swap?	List After
3 vs 5	[3, 5, 1, 2, 8]	No	[3, 5, 1, 2, 8]
5 vs 1	[3, 5, 1, 2, 8]	Yes	[3, 1, 5, 2, 8]
5 vs 2	[3, 1, 5, 2, 8]	Yes	[3, 1, 2, 5, 8]

After Pass 2: [3, 1, 2, 5, 8]

Pass 3

Comparison	List Before	Swap?	List After
3 vs 1	[3, 1, 2, 5, 8]	Yes	[1, 3, 2, 5, 8]
3 vs 2	[1, 3, 2, 5, 8]	Yes	[1, 2, 3, 5, 8]

After Pass 3: [1, 2, 3, 5, 8]

Pass 4

Comparison	List Before	Swap?	List After
1 vs 2	[1, 2, 3, 5, 8]	No	[1, 2, 3, 5, 8]

No swaps made — the list is sorted. Algorithm terminates.

Final result: [1, 2, 3, 5, 8]

---

Efficiency of Bubble Sort

Case	Comparisons	Explanation
Best case	O(n)	List is already sorted (with early exit optimisation)
Worst case	O(n²)	List is in reverse order
Average case	O(n²)	Roughly n²/2 comparisons and swaps

Bubble sort is not efficient for large datasets because the number of comparisons grows quadratically as the list gets bigger.

---

Advantages of Bubble Sort

• Simple to understand and implement
• Easy to detect if the list is already sorted (no swaps in a pass)
• Does not require extra memory — it sorts in place (space complexity O(1))
• Good for small datasets or nearly sorted data

Disadvantages of Bubble Sort

• Very slow for large datasets — O(n²) comparisons
• Inefficient compared to merge sort, quicksort, and insertion sort
• Not used in practice for real-world applications with large data

Exam Tip: If asked to describe or trace through a bubble sort, show each pass clearly. Mark which elements are compared and whether they are swapped. State when the algorithm terminates and why (no swaps in a complete pass).

---

Key Points

• Bubble sort compares adjacent elements and swaps them if in the wrong order.
• Each pass moves the next-largest element to its correct position.
• The algorithm stops when a complete pass is made with no swaps.
• Time complexity: O(n²) in the worst and average case; O(n) best case with optimisation.
• Simple but slow — suitable only for small or nearly sorted datasets.

---

Extended Worked Examples

Worked Example A: Sorting a Longer List

Sort the list [9, 4, 7, 2, 6, 1] using bubble sort. We show every comparison and swap.

Pass 1 (n − 1 = 5 comparisons)

Index pair	Before	Compare	Swap?	After
(0,1)	[9,4,7,2,6,1]	9 > 4	Yes	[4,9,7,2,6,1]
(1,2)	[4,9,7,2,6,1]	9 > 7	Yes	[4,7,9,2,6,1]
(2,3)	[4,7,9,2,6,1]	9 > 2	Yes	[4,7,2,9,6,1]
(3,4)	[4,7,2,9,6,1]	9 > 6	Yes	[4,7,2,6,9,1]
(4,5)	[4,7,2,6,9,1]	9 > 1	Yes	[4,7,2,6,1,9]