Bubble Sort in C and C++: Step-by-Step Passes, Early Exit and Complexity

On 1,000 random integers, the swapped-flag early exit for bubble sort saved 136 of 499,500 comparisons. On the same 1,000 integers already in order, it saved 498,501. Those two numbers explain most of bubble sort. It is simple and stable, and it finishes in a few passes when no value has far to travel toward the front of the array. One small value stranded at the back is enough to make it quadratic.

This guide traces bubble sort pass by pass, then gives a clean C implementation, a generic C++ version that needs only forward iterators (so it also sorts a std::forward_list), measured comparison counts for five input shapes, and the four bugs that compile without a single warning. Every program on this page was compiled and run on Ubuntu 24.04 with GCC 13.3 and Clang 18.1.3 (C under -std=c11 and -std=c17, C++ under -std=c++17 and -std=c++20) with -Wall -Wextra -pedantic and no warnings, and the tests ran clean under AddressSanitizer and UndefinedBehaviorSanitizer. Every output block is captured verbatim, and the code lives in two GitHub repositories whose builds run the same tests on every change to the example.

What Is Bubble Sort?

Bubble sort is a comparison sorting algorithm that repeatedly walks through a sequence, such as an array, compares each pair of neighboring elements, and swaps them when they are out of order. After each pass the largest remaining value has moved to the end, so the next pass can stop one position earlier. It sorts in place, is stable, and takes O(n²) time on average and in the worst case.

The name comes from the way large values travel toward the end of the array one swap at a time, like bubbles rising. Owen Astrachan’s history of the algorithm traces how it became a textbook staple despite its performance, and cites Donald Knuth’s verdict that it has “nothing to recommend it, except a catchy name.” It is still worth learning: it is the shortest correct sort you can write from memory, and its failure modes teach a lot about loop bounds, stability and measurement.

How Bubble Sort Works, Step by Step

1. Compare a[0] and a[1]. If the left one is larger, swap them.
2. Move right one position and repeat for a[1] and a[2], then a[2] and a[3], until the end of the unsorted part.
3. One pass is done. The largest value in the unsorted part is now at its end, in its final position.
4. Shrink the unsorted part and start the next pass from a[0].
5. Stop when a pass makes no swaps. The array is sorted.

Here is every comparison bubble sort makes on the array 7 3 9 2 11 15, printed by the trace program in the repository:

Pass 2 compares only three positions, not five. Pass 1 made its last swap at a[2]:a[3], so nothing after a[3] moved, and 9 11 15 were already in their final places. Tracking where the last swap happened lets the next pass stop there. That is the version implemented below: 8 comparisons here, against 15 for the textbook loop that always runs n − 1 full passes.

Bubble Sort in C

This program sorts a small array, an array holding INT_MIN and INT_MAX, a single element and an empty array:

/* bubble_sort.c - bubble sort in C with early exit */
#include <stdio.h>
#include <stddef.h>
#include <limits.h>

/* Sorts a[0..n-1] in ascending order. Stable, in place, O(1) extra memory. */
void bubble_sort(int a[], size_t n)
{
    size_t bound = n;               /* a[bound..n-1] is in its final position */

    while (bound > 1) {
        size_t last_swap = 0;

        for (size_t j = 1; j < bound; j++) {
            if (a[j] < a[j - 1]) {  /* strict <: equal values never swap */
                int tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
                last_swap = j;
            }
        }
        bound = last_swap;          /* no swaps -> 0 -> loop ends */
    }
}

static void print_array(const char *label, const int a[], size_t n)
{
    printf("%-10s", label);
    for (size_t i = 0; i < n; i++)
        printf(" %d", a[i]);
    printf("\n");
}

int main(void)
{
    int data[] = { 7, 3, 9, 2, 11, 15 };
    int edge[] = { 0, INT_MAX, -1, INT_MIN, 0, 42 };
    int one[]  = { 5 };

    size_t n_data = sizeof data / sizeof data[0];
    size_t n_edge = sizeof edge / sizeof edge[0];

    print_array("before:", data, n_data);
    bubble_sort(data, n_data);
    print_array("after:", data, n_data);

    bubble_sort(edge, n_edge);
    print_array("limits:", edge, n_edge);

    bubble_sort(one, 1);            /* one element: nothing to do */
    bubble_sort(NULL, 0);           /* empty: the loop never runs  */
    print_array("single:", one, 1);
    return 0;
}

Output:

before:    7 3 9 2 11 15
after:     2 3 7 9 11 15
limits:    -2147483648 -1 0 0 42 2147483647
single:    5

Four details in this function do most of the work:

• bound replaces the swapped flag. It records the index of the last swap. A pass with no swaps leaves it at 0, which ends the loop, so the early exit comes for free. A pass that swaps only near the front shrinks the next pass by more than one position.
• The comparison is strict. a[j] < a[j - 1] never swaps two equal values, which is what makes the sort stable. Using <= breaks stability, as the mistakes section shows.
• Lengths are size_t, and the loop never computes n - 1. The condition bound > 1 is safe for n == 0, which is why bubble_sort(NULL, 0) returns without touching memory.
• Values are only compared, never subtracted, so INT_MIN and INT_MAX sort correctly with no overflow.

To sort in descending order, change a[j] < a[j - 1] to a[j] > a[j - 1]. Keep it strict to keep the sort stable.

The Classic Swapped-Flag Version

This is the swapped-flag form. It shrinks the pass by exactly one position each time and stops after the first pass with no swaps. It is a drop-in replacement for bubble_sort() above:

/* bubble_sort_flag.c - the classic swapped-flag version, for comparison */
#include <stddef.h>

void bubble_sort_flag(int a[], size_t n)
{
    for (size_t pass = 1; pass < n; pass++) {
        int swapped = 0;
        for (size_t j = 1; j <= n - pass; j++) {
            if (a[j] < a[j - 1]) {
                int tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped)           /* a pass with no swaps: already sorted */
            break;
    }
}

Both versions produce identical results on 10,000 test arrays in the repository. The boundary version never makes more comparisons than the flag version, and the next section measures how often it makes fewer.

Bubble Sort in C++

In C++ the same algorithm becomes a template that takes an iterator range and a comparator, like the standard algorithms do. Because it only ever steps forward and compares neighbors, it needs nothing stronger than a forward iterator:

// bubble_sort.cpp - generic bubble sort in C++17
#include <algorithm>
#include <forward_list>
#include <functional>
#include <iostream>
#include <iterator>
#include <string>
#include <utility>
#include <vector>

// Sorts [first, last) so that comp(b, a) is false for every adjacent pair a, b.
// Needs only forward iterators. Stable: equal elements are never swapped.
template <class ForwardIt, class Compare = std::less<>>
void bubble_sort(ForwardIt first, ForwardIt last, Compare comp = {})
{
    if (first == last)
        return;

    ForwardIt end = last;                 // [end, last) is in final position
    for (;;) {
        ForwardIt last_swap = first;
        ForwardIt prev = first;
        for (ForwardIt cur = std::next(first); cur != end; ++prev, ++cur) {
            if (comp(*cur, *prev)) {
                std::iter_swap(prev, cur);
                last_swap = cur;
            }
        }
        if (last_swap == first)           // a full pass with no swaps
            return;
        end = last_swap;
    }
}

template <class Range>
void print(const char* label, const Range& r)
{
    std::cout << label;
    for (const auto& x : r) std::cout << ' ' << x;
    std::cout << '\n';
}

struct Employee {
    std::string name;
    int dept;
};

int main()
{
    std::vector<int> v{7, 3, 9, 2, 11, 15};
    bubble_sort(v.begin(), v.end());
    print("ascending: ", v);

    bubble_sort(v.begin(), v.end(), std::greater<>{});
    print("descending:", v);

    // A singly linked list: std::sort cannot take it, bubble_sort can.
    std::forward_list<std::string> words{"pear", "fig", "apple", "kiwi"};
    bubble_sort(words.begin(), words.end());
    print("words:     ", words);

    // Stability: sort by department only; names within a department keep order.
    std::vector<Employee> staff{
        {"Ava", 2}, {"Ben", 1}, {"Cleo", 2}, {"Dev", 1}, {"Eli", 3}, {"Fay", 1}};
    auto expected = staff;
    auto by_dept = [](const Employee& a, const Employee& b) { return a.dept < b.dept; };

    bubble_sort(staff.begin(), staff.end(), by_dept);
    std::stable_sort(expected.begin(), expected.end(), by_dept);

    std::cout << "by dept:   ";
    for (const auto& e : staff) std::cout << ' ' << e.dept << ':' << e.name;
    std::cout << '\n';

    bool same = std::equal(staff.begin(), staff.end(), expected.begin(),
                           [](const Employee& a, const Employee& b) {
                               return a.name == b.name && a.dept == b.dept;
                           });
    std::cout << "matches std::stable_sort: " << (same ? "yes" : "no") << '\n';
    return 0;
}

Output:

ascending:  2 3 7 9 11 15
descending: 15 11 9 7 3 2
words:      apple fig kiwi pear
by dept:    1:Ben 1:Dev 1:Fay 2:Ava 2:Cleo 3:Eli
matches std::stable_sort: yes

What the output shows:

• The comparator follows the standard convention. comp(a, b) means “a goes before b”, so std::greater<>{} sorts in descending order with no change to the function. The swap happens only when comp(*cur, *prev) is true, which keeps equal elements in their original order.
• It works on a std::forward_list. std::sort needs random-access iterators, and passing it a forward_list fails to compile with GCC’s error: no match for 'operator-'. In real code you would call the list’s own sort() member instead, but the example shows how few requirements bubble sort places on its input.
• The stability check is against the standard library, not against expectations. Ben, Dev and Fay keep their input order within department 1, and the result matches std::stable_sort element for element. The repository test repeats this on 5,000 random inputs with heavy key duplication, over std::vector, std::forward_list and std::list.

Does the Early Exit Actually Help? Comparison Counts

To see what each optimization buys, the counting program in the repository sorts 1,000 integers in five arrangements with three bubble sort variants and, for contrast, insertion sort:

• plain: n − 1 passes, each one element shorter, no early exit
• flag: the swapped-flag version above
• boundary: the last-swap version used in this article
• insertion: a standard insertion sort

The random input comes from a fixed-seed xorshift generator rather than rand(), whose sequence differs between C libraries, so the numbers reproduce on any platform. (See generating random numbers in C and C++ for the trade-offs.)

Output:

comparisons, n = 1000
input              plain      flag  boundary  insertion    swaps
sorted            499500       999       999        999        0
random            499500    499364    494153     244344   243354
reversed          499500    499500    499500     499500   499500
smallest-last     499500    499500    499500       1997      999
largest-first     499500      1997      1997       1997      999
every variant's swap count equals the independently counted inversions

The table makes five points:

• Without an early exit, the input does not matter. The plain loop makes n(n − 1)/2 = 499,500 comparisons on every input, including one that is already sorted.
• On random data, the early exit barely helps. The flag saved 136 comparisons (0.03%) and the boundary saved 5,347 (1.1%). Random data needs almost every pass.
• The early exit helps only when no element has far to travel toward the front. A large value near the front (largest-first, a “rabbit”) moves to the end in a single pass, so the flag stops after two passes: 1,997 comparisons. A small value near the end (smallest-last, a “turtle”) moves only one position left per pass, so it needs every pass: 499,500 comparisons for an array with just 999 elements out of place.
• Swaps equal inversions. Each adjacent swap removes exactly one inversion, a pair of elements in the wrong order, so every variant makes the same number of swaps: the number of inversions in the input. The program counts inversions separately with a merge sort and checks the two agree. For random input the expected count is n(n − 1)/4 = 249,750; this run measured 243,354, about 1.2 standard deviations below that expectation.
• Insertion sort handles both cases. Its comparisons track the number of inversions plus at most n − 1, so the turtle costs it 1,997 comparisons instead of 499,500, and random data costs it half as many as bubble sort.

Bubble Sort Time and Space Complexity

The O(n) best case depends on the early exit. The plain loop is O(n²) on every input, including sorted input, as the counts above show.

How the Timing Was Measured

No CPU pinning, frequency-scaling control or variance statistics were captured, and all figures come from this one machine. Treat the ratios as indications, not constants. The timing program is bubble_time.c in the repository.

Bubble Sort vs qsort: Timings

Output (GCC 13.3, -O2):

       n    bubble (ms)   qsort (ms)    ratio
    1000           1.95         0.08      25x
    5000          54.82         0.42     130x
   20000        1065.23         2.00     532x

Growing n by 4× (5,000 to 20,000) made bubble sort about 19× slower and qsort about 5× slower. That is the difference between O(n²) and O(n log n) showing up at sizes well within what ordinary programs sort.

A GCC Surprise: -O2 Was Slower Than -O1

The same program behaved very differently across compiler settings. Bubble sort times for n = 20,000, as the range of three invocations (each itself a median of five runs):

Turning off one optimization, SLP vectorization, took away most of the slowdown. At -O2, GCC loads each neighboring pair as a single 8-byte vector and writes a swapped pair back as one 8-byte store; the generated assembly contains those vector instructions, and with -fno-tree-slp-vectorize it contains none. The next iteration then loads 8 bytes starting 4 bytes into the pair it just stored. GCC’s bug tracker has the same pattern filed against insertion sort as bug 115777, where a GCC maintainer attributes the slowdown to a store-to-load forwarding conflict. That explanation fits these measurements, but no hardware counters were read here to confirm it on this CPU.

The practical lesson is not “use -O1“. It is that a hand-written inner loop can land on a compiler’s blind spot. qsort lives in the prebuilt C library, so none of these flags touched it: it took between 1.9 and 2.2 ms in every run of every configuration. Even in its fastest configuration here, bubble sort was about 180× slower.

Four Bubble Sort Mistakes That Compile Without Warnings

Each program below compiles with -Wall -Wextra -pedantic and no warnings from GCC or Clang. All four are in the repository’s pitfalls/ directory, and the build checks that each one fails the way this section describes: the sanitizers catch the first, second and fourth, and the third is checked by its output.

1. Computing n − 1 With an Unsigned Length

#include <stdio.h>
#include <stddef.h>

void bubble_sort_textbook(int a[], size_t n)
{
    for (size_t i = 0; i < n - 1; i++)          /* n == 0: n - 1 is SIZE_MAX */
        for (size_t j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
            }
}

int main(void)
{
    int buf[1] = { 0 };
    bubble_sort_textbook(buf, 0);               /* an empty array */
    puts("done");
    return 0;
}

With size_t n = 0, n - 1 wraps around to the largest size_t value, and the loop reads far past the array. The GCC -O2 build crashed with a segmentation fault; the Clang -O2 build printed done and exited normally; AddressSanitizer reported:

==1457==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7f3d44100024 at pc 0x55cae452d314 bp 0x7ffde9308bf0 sp 0x7ffde9308be0
READ of size 4 at 0x7f3d44100024 thread T0
    #0 0x55cae452d313 in bubble_sort_textbook pitfalls/underflow.c:8
    #1 0x55cae452d563 in main pitfalls/underflow.c:16

A build that prints done is not evidence the code is correct. Write loop conditions that add instead of subtract (i + 1 < n), or use the bound > 1 form from the C program above.

2. An Off-by-One in the Inner Loop

#include <stdio.h>
#include <stddef.h>

void bubble_sort_off_by_one(int a[], size_t n)
{
    for (size_t i = 0; i + 1 < n; i++)
        for (size_t j = 0; j < n - i; j++)      /* should be j + 1 < n - i */
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
            }
}

int main(void)
{
    int a[] = { 3, 1, 2 };
    bubble_sort_off_by_one(a, 3);
    printf("%d %d %d\n", a[0], a[1], a[2]);
    return 0;
}

On the first pass, j reaches 2, so the code compares and may swap a[2] with a[3], one element past the end. This is undefined behavior, and six builds of the same source gave five different results:

The Clang -O2 result is the most instructive. The generated assembly for main contained no instructions at all, which is consistent with the optimizer treating the out-of-bounds access as unreachable and discarding everything that led to it. Two of the five builds without a sanitizer print the right answer, which is how a bug like this survives testing.

3. Using <= Instead of < (Stability)

This program sorts records by key twice, once with a strict comparison and once with <=. The letter tags show the original order of equal keys:

#include <stdio.h>
#include <stddef.h>

typedef struct { int key; char tag; } Item;

void sort_by_key(Item a[], size_t n, int use_lte)
{
    size_t bound = n;
    while (bound > 1) {
        size_t last_swap = 0;
        for (size_t j = 1; j < bound; j++) {
            int out_of_order = use_lte ? a[j].key <= a[j - 1].key
                                       : a[j].key <  a[j - 1].key;
            if (out_of_order) {
                Item t = a[j]; a[j] = a[j - 1]; a[j - 1] = t;
                last_swap = j;
            }
        }
        bound = last_swap;
    }
}

static void show(const char *label, const Item a[], size_t n)
{
    printf("%s", label);
    for (size_t i = 0; i < n; i++)
        printf(" %d%c", a[i].key, a[i].tag);
    printf("\n");
}

int main(void)
{
    Item x[] = { {2,'a'}, {1,'b'}, {2,'c'}, {1,'d'}, {2,'e'} };
    Item y[] = { {2,'a'}, {1,'b'}, {2,'c'}, {1,'d'}, {2,'e'} };
    size_t n = sizeof x / sizeof x[0];

    show("input:        ", x, n);
    sort_by_key(x, n, 0);
    show("strict  <  :  ", x, n);
    sort_by_key(y, n, 1);
    show("with    <= :  ", y, n);
    return 0;
}

Output:

input:         2a 1b 2c 1d 2e
strict  <  :   1b 1d 2a 2c 2e
with    <= :   1d 1b 2e 2c 2a

Both results are sorted by key, so a test that only checks sortedness passes both. In this output the <= version reversed both groups of equal keys. With the classic do { ... } while (swapped) loop, which does not shrink the pass, <= is worse still: two equal neighbors swap on every pass, so swapped never stays 0. A test program in the repository (pitfalls/do_while_lte.c) finished {3, 1, 2} in two passes but was still swapping {3, 1, 3} after 1,000,000 passes.

4. A Comparator That Subtracts

Replacing a hand-written sort with qsort() moves the comparison into a comparator function, and that is another place overflow can hide:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

static int cmp_subtract(const void *pa, const void *pb)
{
    return *(const int *)pa - *(const int *)pb;     /* overflows */
}

static int cmp_safe(const void *pa, const void *pb)
{
    int a = *(const int *)pa, b = *(const int *)pb;
    return (a > b) - (a < b);
}

int main(void)
{
    int x[] = { 1, INT_MIN, 0, INT_MAX, -1 };
    int y[] = { 1, INT_MIN, 0, INT_MAX, -1 };
    size_t n = sizeof x / sizeof x[0];

    qsort(x, n, sizeof x[0], cmp_subtract);
    qsort(y, n, sizeof y[0], cmp_safe);

    printf("subtract:");
    for (size_t i = 0; i < n; i++) printf(" %d", x[i]);
    printf("\ncompare: ");
    for (size_t i = 0; i < n; i++) printf(" %d", y[i]);
    printf("\n");
    return 0;
}

Output:

subtract: 0 1 2147483647 -2147483648 -1
compare:  -2147483648 -1 0 1 2147483647

1 - INT_MIN does not fit in an int, and UndefinedBehaviorSanitizer reports it directly: runtime error: signed integer overflow: 1 - -2147483648 cannot be represented in type 'int'. The (a > b) - (a < b) form returns −1, 0 or 1 without any arithmetic that can overflow.

When Not to Use Bubble Sort (and What to Use Instead)

Bubble sort is a reasonable choice when the goal is to learn or teach how sorting works, when you need a few lines of stable, allocation-free code for a handful of elements, or when the data is known to be sorted except for a few large values out of place. For anything else, one of these is a better fit:

The C standard specifies neither the algorithm nor the complexity of qsort(), and it does not require stability. C++’s std::sort is specified to make O(n log n) comparisons and does not preserve the order of equal elements; use std::stable_sort when order matters.

Insertion sort is the closest replacement in its own class: the counts above show it doing half of bubble sort’s comparisons on random data and handling the turtle case in linear time. Shell sort builds on insertion sort to break the O(n²) barrier with no recursion and no extra memory, and quicksort is the divide-and-conquer design that GCC’s std::sort builds on, as part of the introsort hybrid. In application code, call the library sort.

Key Takeaways

• Bubble sort swaps neighboring elements until a pass makes no swaps. Each pass puts the largest remaining value in its final position.
• Track the last swap, not just whether one happened. The boundary version gives the early exit for free and can skip several finished positions in one step.
• The O(n) best case depends on the early exit. Without it, bubble sort makes n(n − 1)/2 comparisons even on sorted input.
• The early exit helps only with the right kind of disorder. One small element at the end still costs the full 499,500 comparisons for n = 1,000; on random data the flag saved 0.03%.
• Keep the comparison strict. < makes bubble sort stable; <= silently reorders equal keys.
• Guard the loop bounds. n - 1 on an unsigned zero and an inner loop that reaches a[n] both compile without warnings and can print correct output until they do not.
• Use qsort(), std::sort or std::stable_sort in real code. At 20,000 elements, bubble sort was about 180× to 530× slower than qsort() on the test machine.

Frequently Asked Questions

Conclusion

Bubble sort earns its place in a curriculum for the same reason production code rarely uses it: its weaknesses are easy to see. You can watch a turtle crawl left one position per pass, count the swaps and find they equal the inversions, and see a one-character change to the comparison break stability without breaking the output. Those habits of tracing, counting and testing against a trusted reference carry over to the algorithms you write afterward.

The natural next steps are the algorithms that fix what bubble sort gets wrong: insertion sort for nearly sorted data, Shell sort for moving elements long distances, and the divide-and-conquer sorts that reach O(n log n). The algorithms section covers them with the same tested, measured approach.

Source Code and Tests

The C code is in mycplus/c-examples/sorting/bubble-sort and the C++ code in mycplus/cpp-examples/sorting/bubble-sort .

c-examples/sorting/bubble-sort/
├── CMakeLists.txt
├── src/          bubble_sort.c  bubble_sort_flag.c  bubble_trace.c
│                 bubble_count.c  bubble_time.c
├── pitfalls/     underflow.c  off_by_one.c  stability.c  comparator.c
│                 do_while_lte.c
└── tests/        test_bubble_sort.c  test_flag.c  expected/  compare_output.cmake

cpp-examples/sorting/bubble-sort/
├── CMakeLists.txt
├── src/          bubble_sort.cpp
└── tests/        test_bubble_sort.cpp  expected/  compare_output.cmake

Build and test either one with:

cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure

What the build checks on each change to the example:

• Compilation with warnings as errors: GCC and Clang with -Wall -Wextra -pedantic -Werror (C11 and C17; C++17 and C++20), and MSVC with /W4 /WX.
• Correctness against a reference: the C function against qsort() on 20,000 random arrays of 0 to 64 elements, including INT_MIN, INT_MAX and many duplicates; the C++ template against std::stable_sort on 5,000 inputs over three container types, which checks stability as well as order.
• The printed output on this page: the C program’s output and the comparison-count table are compared byte for byte with the blocks above, and the trace program’s output with the file the pass table was transcribed from.
• Sanitizers: the tests run under AddressSanitizer and UndefinedBehaviorSanitizer, and the build confirms that the sanitizers catch the out-of-bounds reads and the comparator overflow in the pitfalls/ programs, and that the two <= programs misbehave exactly as described.

The build does not run the timing program, because timings depend on the machine and are not a pass/fail property. A green badge means the code compiles on those toolchains and passes those tests; it does not reproduce the timing figures above.