Bubble Sort
The classic comparison-based sorting algorithm. Large values "bubble up" to the right in each pass. Learn the standard algorithm, trace it pass by pass, and understand the early termination optimisation that can make it far more efficient.
Sorting is one of the most fundamental operations in computing. Searching is faster on sorted data. Merging two lists is easier when both are sorted. Presenting results in alphabetical or numerical order requires sorting. Bubble sort is the simplest sorting algorithm to understand, trace and describe - which is why it appears frequently in exam questions. It is rarely used in production software (merge sort and quicksort are far faster for large lists), but mastering bubble sort builds the intuition you need for all other sorting algorithms.
Bubble sort works in passes. In each pass, it compares every adjacent pair of elements and swaps them if the left element is greater than the right. After each pass, the largest unsorted element has "bubbled" to its correct position at the right.
After pass 1, the largest element is at the last position. After pass 2, the second-largest is at the second-to-last position. After n-1 passes, all elements are sorted.
To swap two elements without losing data, a temporary variable (temp) is used:
// Swap myList[i] and myList[i+1] using a temp variable temp ← myList[i] // Save the first value myList[i] ← myList[i+1] // Overwrite first with second myList[i+1] ← temp // Overwrite second with saved first
# Swap myList[i] and myList[i+1]
temp = myList[i]
myList[i] = myList[i+1]
myList[i+1] = tempWithout temp: if you write myList[i] = myList[i+1] first, the original value of myList[i] is overwritten and permanently lost. You can no longer assign it to myList[i+1]. The temp variable stores the first value safely while the assignment takes place.
// Bubble sort - sorts myList into ascending order (AQA) SUBROUTINE bubbleSort(myList) n ← LEN(myList) FOR pass ← 1 TO n - 1 FOR i ← 0 TO n - pass - 1 IF myList[i] > myList[i+1] THEN temp ← myList[i] myList[i] ← myList[i+1] myList[i+1] ← temp ENDIF ENDFOR ENDFOR RETURN myList ENDSUBROUTINE
# Bubble sort - sorts myList into ascending order (OCR) procedure bubbleSort(myList) n = len(myList) for pass = 1 to n - 1 for i = 0 to n - pass - 1 if myList[i] > myList[i+1] then temp = myList[i] myList[i] = myList[i+1] myList[i+1] = temp end if next i next pass return myList endprocedure
After pass 1, the largest element is correctly placed at position n-1. After pass 2, the second-largest is at n-2. So with each pass, one fewer comparison is needed. The inner loop boundary n - pass - 1 avoids comparing already-sorted elements, saving a small amount of unnecessary work.
Trace bubble sort on [64, 25, 12, 22, 11]:
| Pass | After pass | Swaps made? |
|---|---|---|
| Start | [64, 25, 12, 22, 11] | - |
| Pass 1 | [25, 12, 22, 11, 64] | Yes (64 bubbles to end) |
| Pass 2 | [12, 22, 11, 25, 64] | Yes |
| Pass 3 | [12, 11, 22, 25, 64] | Yes |
| Pass 4 | [11, 12, 22, 25, 64] | Yes - all sorted |
Green = confirmed in final position. 4 passes (n-1 = 5-1) for a 5-element list.
Pass 1 detail - comparing every adjacent pair:
| Compare | Values | Swap? | List after |
|---|---|---|---|
| i=0: [0] vs [1] | 64 vs 25 | Yes (64>25) | [25, 64, 12, 22, 11] |
| i=1: [1] vs [2] | 64 vs 12 | Yes | [25, 12, 64, 22, 11] |
| i=2: [2] vs [3] | 64 vs 22 | Yes | [25, 12, 22, 64, 11] |
| i=3: [3] vs [4] | 64 vs 11 | Yes | [25, 12, 22, 11, 64] |
64 "bubbled up" to the end in one pass. 4 comparisons made in pass 1.
Exam questions on bubble sort commonly ask you to: (1) Show the list after each pass. (2) State how many comparisons a specific pass makes. (3) Identify when the algorithm would terminate early. Always show the swap using a temp variable when writing the algorithm. Know that after pass k, the last k elements are in their correct final positions.
Standard bubble sort always runs n-1 passes regardless of whether the list is already sorted. The early termination optimisation uses a boolean flag (swapped): if a complete pass makes no swaps at all, the list must already be sorted - stop immediately.
// Bubble sort with early termination (AQA) SUBROUTINE bubbleSortOptimised(myList) n ← LEN(myList) swapped ← TRUE pass ← 0 WHILE swapped = TRUE swapped ← FALSE // Assume sorted this pass FOR i ← 0 TO n - pass - 2 IF myList[i] > myList[i+1] THEN temp ← myList[i] myList[i] ← myList[i+1] myList[i+1] ← temp swapped ← TRUE // A swap was made ENDIF ENDFOR pass ← pass + 1 ENDWHILE RETURN myList ENDSUBROUTINE
# Bubble sort with early termination (OCR) procedure bubbleSortOptimised(myList) n = len(myList) swapped = true pass = 0 while swapped == true swapped = false for i = 0 to n - pass - 2 if myList[i] > myList[i+1] then temp = myList[i] myList[i] = myList[i+1] myList[i+1] = temp swapped = true end if next i pass = pass + 1 end while return myList endprocedure
With early termination, if the list is already sorted, only one pass is needed (to confirm no swaps are necessary). Without early termination, bubble sort would still run n-1 passes even on a sorted list. This makes the best case O(n) with early termination, compared to O(n2) without it.
Press Sort to watch the animated bubble sort. Orange bars are being compared. Red bars are being swapped. Green bars are in their final sorted position.
Test yourself
1. After the first complete pass of bubble sort on [5, 3, 8, 1, 9, 2], which element is guaranteed to be in its final sorted position?
2. Why is a temporary variable (temp) needed when swapping two elements?
3. A list of 7 elements is sorted using bubble sort. What is the maximum number of passes needed?
4. What does the early termination optimisation detect to stop the sort early?
5. Bubble sort has worst-case complexity O(n2). Which input causes the worst case?
A student claims that bubble sort with early termination is always better than standard bubble sort. Describe a specific scenario where early termination makes a significant difference and another where it makes no difference at all. Then state the best and worst case number of passes for each scenario on a list of 100 items.
If the list is already sorted (e.g. [1,2,3,...,100]). Without early termination: 99 passes regardless. With early termination: just 1 pass (confirms no swaps needed), then stops. This is the best case for optimised bubble sort: O(n) = 100 comparisons total instead of O(n2) = ~4950.
Early termination makes no difference:
If the list is in reverse sorted order (e.g. [100,99,98,...,1]). Every pass will make at least one swap, so the early termination flag never stays false. Both versions run the full n-1 = 99 passes.
Summary:
Best case with early termination: 1 pass (list already sorted)
Worst case with early termination: 99 passes (reverse sorted list)
Standard bubble sort: always 99 passes regardless of input order.
Practice what you have learned
Three levelled worksheets. Download, print and complete offline.