Bubble Sort repeatedly steps through the array, comparing each pair of adjacent elements and swapping them if they're in the wrong order. Each full pass "bubbles" the largest remaining unsorted element up to its correct position at the end of the array. The process repeats for n−1 passes, or stops early the moment a full pass makes zero swaps (a clear sign the array is already sorted).
BUBBLE_SORT(arr, n):
FOR i = 0 TO n-2:
swapped = FALSE
FOR j = 0 TO n-2-i: // unsorted region shrinks by 1 each pass
IF arr[j] > arr[j+1]:
SWAP(arr[j], arr[j+1])
swapped = TRUE
IF NOT swapped: BREAK // early-exit optimization — already sorted
| Case | Time | When |
|---|---|---|
| Best | O(n) | Array already sorted — only 1 pass needed, with the swapped-flag optimization |
| Average | O(n²) | Random order |
| Worst | O(n²) | Reverse-sorted — every possible pair is out of order |
Space: O(1) (in-place, only a temp variable for swapping). Stable: yes — equal elements never cross past each other, since a swap only happens on strict >.
Bubble Sort's O(n²) worst/average case is why it's the textbook example of an inefficient sort — but its O(n) best case (with early exit) and O(1) space make it a fair answer for "which sort would you use on a tiny or nearly-sorted array." The exam format is almost always a pass-by-pass trace: write out the array after every single pass, not just the final sorted result — examiners award marks per pass shown.
2017, Paper I, Q5(c) (6 marks) — Describe the process of Bubble Sorting. Write down the output after each pass of the Bubble Sort algorithm for sorting the sequence (3, 8, 2, 6, 1, 10).
Starting array: [3, 8, 2, 6, 1, 10], n = 6
Pass 1 (compare positions 0↔1, 1↔2, 2↔3, 3↔4, 4↔5):
3,8→no swap · 8,2→swap · 8,6→swap · 8,1→swap · 8,10→no swap
After Pass 1: [3, 2, 6, 1, 8, 10] — the largest remaining element (8, among the first 5) has bubbled into position 4.
Pass 2: 3,2→swap · 3,6→no swap · 6,1→swap · 6,8→no swap
After Pass 2: [2, 3, 1, 6, 8, 10]
Pass 3: 2,3→no swap · 3,1→swap · 3,6→no swap
After Pass 3: [2, 1, 3, 6, 8, 10]