C++UCS301
Sorting AlgorithmsC++17

Bubble Sort

Bubble sort repeatedly swaps adjacent inversions, moving the largest remaining value to the end of each pass.

Open this in the visual lab

What to understand

  • Adjacent swaps
  • Shrinking unsorted range
  • Early-exit optimisation
  • Stability

Remember this

  1. 1Stable and in-place
  2. 2Adaptive with a swapped flag
  3. 3Mostly educational; inefficient at scale

Detailed notes

Each bubble-sort comparison fixes a local inversion. After one complete pass, the maximum element in the active prefix has moved to its final position, creating a sorted suffix.

A swapped flag makes the algorithm adaptive by stopping when a pass finds no inversions. Despite stability and simplicity, repeated adjacent writes make it unsuitable for large inputs.

How it works

  1. 1Compare adjacent elements in the unsorted prefix.
  2. 2Swap when they are inverted.
  3. 3Shrink the active end after every pass.
  4. 4Stop early when a pass performs no swap.

Worked trace

One bubble-sort pass

[5, 1, 4, 2]
  1. 1Compare 5 and 1; swap → [1,5,4,2].
  2. 2Compare 5 and 4; swap → [1,4,5,2].
  3. 3Compare 5 and 2; swap → [1,4,2,5].
  4. 4The largest value 5 is now final.
Result: Sorted suffix: [5]; repeat on the first three values

Where it is used

  • Teaching loop invariants and stability
  • Detecting whether a tiny range is already sorted
  • Situations where only adjacent exchanges are permitted

Common mistakes

  • Running the inner loop through the sorted suffix
  • Forgetting to reset swapped each pass
  • Using bubble sort for production-scale data

Complexity analysis

OperationBestAverageWorstExtra space
SortO(n)O(n²)O(n²)O(1)

C++ implementation

C++17 reference
main.cpp

Optimised bubble sort

If a full pass makes no swap, the range is already sorted.

void bubbleSort(vector<int>& values) {
    for (int end = values.size() - 1; end > 0; --end) {
        bool swapped = false;
        for (int i = 0; i < end; ++i) {
            if (values[i] > values[i + 1]) {
                swap(values[i], values[i + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}
12 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.