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]