Bubble Sort in C: Optimized Program, Trace and Stability

Bubble sort in C compares neighboring elements and swaps each inverted pair. After one left-to-right pass the largest remaining value has moved to the right edge. A swapped flag stops the algorithm when a complete pass makes no changes. This optimized version is stable, uses O(1) extra space, and is useful for learning—not for sorting large random datasets.

Adjacent bars illustrate comparisons and swaps in bubble sort.

Complete bubble-sort program

The outer loop shrinks the unsorted prefix. The inner index starts at 1, so accessing i - 1 is safe, and stops before the exclusive end bound.

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

void bubble_sort(int values[], size_t count) {
    for (size_t end = count; end > 1; --end) {
        int swapped = 0;
        for (size_t i = 1; i < end; ++i) {
            if (values[i - 1] > values[i]) {
                int temporary = values[i - 1];
                values[i - 1] = values[i];
                values[i] = temporary;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

int main(void) {
    int values[] = {64, 34, 25, 12, 22};
    size_t count = sizeof values / sizeof values[0];
    bubble_sort(values, count);
    for (size_t i = 0; i < count; ++i) {
        printf("%s%d", i == 0 ? "" : " ", values[i]);
    }
    putchar('\n');
    return 0;
}

Run optimized bubble sort online

Expected output

Reference output for the displayed program, not a live execution result.

12 22 25 34 64

Pass-by-pass dry run

Pass Neighbor swaps Array after the pass
Start — 64 34 25 12 22
1 64 crosses 34, 25, 12 and 22 34 25 12 22 64
2 34 crosses 25, 12 and 22 25 12 22 34 64
3 25 crosses 12 and 22 12 22 25 34 64
4 Compare 12 and 22; no swap 12 22 25 34 64

The final pass discovers that no inversions remain in the active prefix. On an already sorted array, the first pass makes no swaps and stops immediately. Reset swapped at the beginning of every pass; otherwise an earlier swap prevents early exit.

Time, space and stability

Case Time Explanation
Best: already sorted O(n) One comparison pass, then early exit
Average, random order O(n²) Many adjacent inversions must be removed
Worst: reverse order O(n²) n(n − 1) / 2 comparisons for this full-pass bound
Auxiliary storage O(1) Indices, flag and one temporary value

This version is stable because it swaps only when the left key is strictly greater than the right key. Equal-key records never cross each other. Using >= needlessly swaps equal keys and can destroy stability. The C sample stores plain integers; labels such as 2a and 2b are only a way to reason about the original identity of equal records.

Bubble sort and insertion sort both have quadratic worst-case time, but insertion sort moves a key through a sorted prefix instead of repeatedly bubbling adjacent values. Selection sort finds a minimum and makes at most one swap per pass; its usual swapping version is not stable.

Array contract and tests to try

The function modifies count writable integers in place. The caller supplies the length; sizeof can calculate that length in main, where values is an array, but not from an array parameter, which adjusts to a pointer. With count zero the function touches nothing and permits a null pointer; positive counts require a valid array. Do not create a nonstandard zero-length array to test empty input.

No stdin is needed. Edit the initializer and run again: {3, -1, 3, 0} should become -1 0 3 3; {2, 2, 2} stays unchanged. Also test one element, ascending order, reverse order and integer extremes. The comparisons do not subtract two integers, so they do not introduce signed overflow when comparing INT_MIN with INT_MAX.

The expected output is a reference, not a fresh compiler execution. The run link loads the exact displayed program and clears old stdin. See arrays for indexing and program structure for the role of headers, functions and main.

Common mistakes and practice

Never read values[i + 1] when i is already the last index. This version uses values[i - 1] and values[i] with an exclusive bound instead. For descending order, change the comparison to strictly less-than. Keep the strict comparison to preserve equality order.

Trace {3, 1, 2} before running: after the first pass it is 1 2 3; the second makes no changes. Then count comparisons on a sorted five-element input: four, not ten, because the optimization stops after one pass. Compare more approaches in the sorting algorithms guide.

Frequently asked questions

Does the swapped flag make bubble sort O(n) in every case?

No. It improves the already-sorted best case. Reverse order and average random inputs still take O(n²) time.

Is bubble sort in place?

This implementation is: it rearranges the original array using O(1) auxiliary storage. In place does not imply stable; those are separate properties.

Related examples