Bubble Sort

Bubble Sort Concept and Loop Invariant

Bubble sort scans adjacent pairs, swaps a pair that is out of order, and repeats passes until no disorder remains. After one complete ascending pass, the largest element in the active range is at its final position. That statement is the pass invariant and explains why the next pass can ignore the sorted suffix.

The result must be ordered and must contain exactly the original elements. This is more important than merely producing the expected output for one example. Compare this elementary method with selection and insertion sort.

Pass-by-Pass Trace

Sort {5, 1, 4, 2, 8} in ascending order:

The third pass makes no swap, so an optimized implementation stops. Without early exit, the output is still correct but needless comparisons continue.

Algorithm and Pseudocode

for end = size down to 2
    swapped = false
    for i = 0 while i + 1 < end
        if values[i] > values[i + 1]
            swap the two values
            swapped = true
    if swapped is false
        stop

end is exclusive. After a pass, values[end-1] is final, so decreasing end is safe. Empty and one-element ranges require no special branch because the outer loop does not run.

Complete Optimized Bubble Sort Program

#include <iostream>
#include <utility>
#include <vector>

void bubble_sort(std::vector<int>& values) {
    for (std::size_t end = values.size(); end > 1; --end) {
        bool swapped = false;
        for (std::size_t i = 0; i + 1 < end; ++i) {
            if (values[i] > values[i + 1]) {
                std::swap(values[i], values[i + 1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

int main() {
    std::vector<int> values{5, 1, 4, 2, 8};
    bubble_sort(values);

    std::cout << "Sorted:";
    for (int value : values) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
}

The function accepts the vector by non-const reference because it intentionally modifies the caller's data. std::size_t matches container sizes, and the end > 1 guard avoids unsigned underflow.

Early Exit and Last-Swap Optimization

The swapped flag changes the best case from quadratic work to one linear pass. A further refinement remembers the position of the last swap: everything after that position was already ordered, so the next active range can end there.

std::size_t end = values.size();
while (end > 1) {
    std::size_t last_swap = 0;
    for (std::size_t i = 1; i < end; ++i) {
        if (values[i - 1] > values[i]) {
            std::swap(values[i - 1], values[i]);
            last_swap = i;
        }
    }
    end = last_swap;
}

This can reduce comparisons on partially sorted data, but it does not change the Θ(n²) average and worst-case growth.

Complexity, Stability and Correctness

Correctness follows from two facts: each pass fixes the largest active element, and swaps preserve the multiset of input values. When a pass makes no swap, every adjacent pair is nondecreasing; by transitivity, the whole range is sorted.

When to Use Bubble Sort

Bubble sort is valuable for visualizing invariants, swaps, stability and asymptotic analysis. It may be acceptable for a tiny range, a classroom demonstration, or code where adjacent exchanges are the exact subject being studied. It is a poor default for large arrays.

Also study the STL algorithms guide before writing a custom production sorter.

Common Mistakes, Tests and Practice

Test set: empty, one element, sorted, reverse sorted, all equal, duplicates, negative values and a large random range. Practice: count comparisons and swaps; implement descending order; implement the last-swap boundary; verify stability using records with equal keys.

Authoritative References

• NIST DADS: bubble sort
• NIST DADS: sort
• C++ Working Draft: sorting and related operations

The definition, complexity classification and standard-library comparison were checked against these sources. Continue with sorting and searching in C++.