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)