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]:

Pass 1:

j	Comparison	Swap?	Array after
0	5 > 3? Yes	Swap	[3, 5, 8, 1, 2]
1	5 > 8? No	—	[3, 5, 8, 1, 2]
2	8 > 1? Yes	Swap	[3, 5, 1, 8, 2]
3	8 > 2? Yes	Swap	[3, 5, 1, 2, 8]

After Pass 1, the largest element (8) is in its final position.

Pass 2:

j	Comparison	Swap?	Array after
0	3 > 5? No	—	[3, 5, 1, 2, 8]
1	5 > 1? Yes	Swap	[3, 1, 5, 2, 8]
2	5 > 2? Yes	Swap	[3, 1, 2, 5, 8]

Pass 3:

j	Comparison	Swap?	Array after
0	3 > 1? Yes	Swap	[1, 3, 2, 5, 8]
1	3 > 2? Yes	Swap	[1, 2, 3, 5, 8]

Pass 4:

j	Comparison	Swap?	Array after
0	1 > 2? No	—	[1, 2, 3, 5, 8]

No swaps occurred — the list is sorted. Final result: [1, 2, 3, 5, 8].

Complexity

Case	Time	Explanation
Best	O(n)	List already sorted — one pass with no swaps
Worst	O(n²)	List in reverse order — maximum swaps
Average	O(n²)
Space	O(1)	In-place sort

---

Insertion Sort

How It Works

Insertion sort builds the sorted list one element at a time. It takes each element and inserts it into its correct position within the already-sorted portion of the list (to the left). Think of it like sorting a hand of playing cards — you pick up each card and slide it into the right place among the cards you already hold.

Pseudocode

PROCEDURE insertionSort(arr, n)
    FOR i = 1 TO n - 1
        key = arr[i]
        j = i - 1
        WHILE j >= 0 AND arr[j] > key
            arr[j + 1] = arr[j]
            j = j - 1
        END WHILE
        arr[j + 1] = key
    END FOR
END PROCEDURE

Trace Table

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