Bubble Sort and Insertion Sort

This lesson covers two fundamental sorting algorithms — bubble sort and insertion sort — as required by the OCR A-Level Computer Science (H446) specification. Understanding how they work, their performance characteristics, and when to use each is essential.

---

Why Sort Data?

Sorting data into a defined order (ascending or descending) is one of the most common operations in computing. Sorted data enables:

• Binary search — O(log n) instead of O(n).
• Efficient merging of data sets.
• Easier data analysis and reporting.
• Duplicate detection.

---

Bubble Sort

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest unsorted element "bubbles" to the end on each pass.

Algorithm

1. Start at the beginning of the list.
2. Compare adjacent pairs of elements.
3. If the left element is greater than the right, swap them.
4. Repeat for the entire list (one pass).
5. After each pass, the largest unsorted element is in its correct position.
6. Repeat passes until no swaps are made (list is sorted).

Pseudocode (OCR Style)

procedure bubbleSort(data, size)
    for i = 0 to size - 2
        swapped = false
        for j = 0 to size - 2 - i
            if data[j] > data[j + 1] then
                temp = data[j]
                data[j] = data[j + 1]
                data[j + 1] = temp
                swapped = true
            endif
        next j
        if swapped == false then
            return    // already sorted — exit early
        endif
    next i
endprocedure

Python Implementation

def bubble_sort(data):
    n = len(data)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
                swapped = True
        if not swapped:
            break    # already sorted
    return data

Worked Example

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

Pass 1:

Comparison	Values	Swap?	Result
[5] vs [3]	5 > 3	Yes	[3, 5, 8, 1, 2]
[5] vs [8]	5 < 8	No	[3, 5, 8, 1, 2]
[8] vs [1]	8 > 1	Yes	[3, 5, 1, 8, 2]
[8] vs [2]	8 > 2	Yes	[3, 5, 1, 2, 8]

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

Pass 2:

Comparison	Values	Swap?	Result
[3] vs [5]	3 < 5	No	[3, 5, 1, 2, 8]
[5] vs [1]	5 > 1	Yes	[3, 1, 5, 2, 8]
[5] vs [2]	5 > 2	Yes	[3, 1, 2, 5, 8]

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

Pass 3: [1, 2, 3, 5, 8] — after further comparisons and swaps.

Pass 4: No swaps needed — algorithm terminates early.

Time Complexity

Case	Description	Comparisons	Complexity
Best	Already sorted (with early exit)	n - 1	O(n)
Worst	Reverse sorted	n(n-1)/2	O(n^2)
Average	Random order	n(n-1)/4	O(n^2)

Space Complexity: O(1) — sorts in place.

---

Insertion Sort

Insertion sort builds the sorted list one element at a time. It takes each element from the unsorted portion and inserts it into its correct position in the sorted portion.

Analogy

Like sorting playing cards in your hand — you pick up one card at a time and insert it into the correct position among the cards you are already holding.

Algorithm