Bubble Sort, Insertion Sort, and Selection Sort

These three sorting algorithms are classified as simple comparison sorts. They are all O(n²) in the worst case, making them unsuitable for large datasets, but they are important to understand because they illustrate fundamental sorting concepts, are straightforward to trace, and appear regularly in A-Level exams.

---

Bubble Sort

How It Works

Bubble sort makes repeated passes through the list. On each pass, it compares adjacent pairs of elements and swaps them if they are in the wrong order. After each pass, the largest unsorted element "bubbles" to its correct position at the end. The algorithm stops when a complete pass is made with no swaps.

Pseudocode

PROCEDURE bubbleSort(arr, n)
    FOR i = 0 TO n - 2
        swapped = FALSE
        FOR j = 0 TO n - 2 - i
            IF arr[j] > arr[j + 1] THEN
                SWAP arr[j], arr[j + 1]
                swapped = TRUE
            END IF
        END FOR
        IF NOT swapped THEN
            RETURN
        END IF
    END FOR
END PROCEDURE

Trace Table

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