C Bubble Sort

Bubble sort is one of the first sorting algorithms most programmers learn, because the idea behind it is so easy to picture: walk through an array comparing neighboring elements, and swap any pair that’s out of order. Do that enough times and the largest values “bubble” up to the end of the array, one per pass, until the whole array is sorted. It isn’t the fastest sorting algorithm — real code almost always uses something better — but it’s an excellent way to practice nested loops, array indexing, and the classic three-line swap in C, and it lays the groundwork for understanding faster algorithms later.

Overview: How Bubble Sort Works

Bubble sort repeatedly scans an array from left to right. On each scan (called a pass), it compares each pair of adjacent elements. If the left element is greater than the right element (for ascending order), it swaps them. After the first full pass, the largest element in the array is guaranteed to be at the last position, because every time it was compared to a smaller neighbor it “won” the comparison and kept moving right. The second pass then guarantees the second-largest element ends up in the second-to-last position, and so on. Because each pass fixes one more element at the end of the array, an array of n elements needs at most n - 1 passes to be fully sorted.

Everything happens in place — bubble sort does not allocate a second array. It only needs a single temporary variable to perform a swap, so its extra memory usage is O(1) regardless of how large the input is. That makes it memory-friendly, even though it isn’t time-friendly: comparing every adjacent pair on every pass means the number of comparisons grows with the square of the input size.

Property	Value
Best-case time	O(n) — only with the early-exit optimization, on an already-sorted array
Average-case time	O(n²)
Worst-case time	O(n²) — reverse-sorted array
Extra space	O(1), sorts in place
Stability	Stable, if you swap only on strict > (never >=)

Bubble sort is also stable: two elements with equal keys never change their relative order, as long as you only swap when one value is strictly greater than the other. The basic version always runs n - 1 passes even if the array becomes sorted early. A very common — and worthwhile — optimization tracks whether any swap happened during a pass; if a whole pass completes with zero swaps, the array is already sorted and the algorithm can stop immediately. That optimization turns bubble sort’s best case into O(n) instead of O(n²), as shown in Example 2 below.

Syntax

Bubble sort isn’t a language keyword — it’s an algorithm you build from two nested loops. The general shape looks like this:

for (i = 0; i < n - 1; i++) {
    for (j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            // swap arr[j] and arr[j + 1]
        }
    }
}

• n — the number of elements in the array.
• i — the outer loop counter; it tracks how many passes have completed, and therefore how many elements at the end of the array are already fixed in place.
• j — the inner loop counter; it walks across the unsorted portion of the array during each pass, comparing arr[j] with its neighbor arr[j + 1].
• n - i - 1 — the upper bound for j. It shrinks by one after every pass because the last i elements are already sorted and don’t need to be re-checked. Getting this bound wrong is the single most common bubble sort bug.
• The swap — written with a temporary variable: temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp;

Examples

Example 1: Basic Ascending Sort

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(void) {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("Sorted array:   ");
    printArray(arr, n);

    return 0;
}

Output:

Original array: 64 34 25 12 22 11 90 
Sorted array:   11 12 22 25 34 64 90 

The bubbleSort function takes the array and its length, then runs the classic double loop: the outer loop controls how many passes to make, and the inner loop compares each adjacent pair up to the unsorted boundary n - i - 1. Whenever arr[j] is bigger than arr[j + 1], the three-line swap exchanges them using temp as scratch space. Because arrays decay to pointers when passed to a function, the swaps performed inside bubbleSort modify the caller’s original array directly — nothing is copied or returned.

Example 2: Optimized Bubble Sort With Early Exit

#include <stdio.h>
#include <stdbool.h>

void bubbleSortOptimized(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;

        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }

        printf("After pass %d: ", i + 1);
        for (int k = 0; k < n; k++) {
            printf("%d ", arr[k]);
        }
        printf("\n");

        if (!swapped) {
            printf("No swaps in this pass - array is sorted early.\n");
            break;
        }
    }
}

int main(void) {
    int arr[] = {5, 1, 4, 2, 8};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSortOptimized(arr, n);

    return 0;
}

Output:

After pass 1: 1 4 2 5 8 
After pass 2: 1 2 4 5 8 
After pass 3: 1 2 4 5 8 
No swaps in this pass - array is sorted early.

This version adds a bool swapped flag that starts false at the beginning of every pass and becomes true the moment any swap happens. If an entire pass finishes without a single swap, the array must already be sorted, so the function prints a message and breaks out of the outer loop instead of wasting more passes. Here the five-element array is fully sorted after two passes, but a third pass is still needed to confirm no swaps happen before the algorithm can safely stop. Without this optimization, the loop would silently run two more unnecessary passes.

Example 3: Bubble-Sorting an Array of Strings

#include <stdio.h>
#include <string.h>

#define MAX_LEN 20

void bubbleSortStrings(char arr[][MAX_LEN], int n) {
    char temp[MAX_LEN];
    int totalSwaps = 0;

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (strcmp(arr[j], arr[j + 1]) > 0) {
                strcpy(temp, arr[j]);
                strcpy(arr[j], arr[j + 1]);
                strcpy(arr[j + 1], temp);
                totalSwaps++;
            }
        }
    }

    printf("Total swaps: %d\n", totalSwaps);
}

int main(void) {
    char names[][MAX_LEN] = {"Charlie", "Alice", "Eve", "Bob", "Dave"};
    int n = 5;

    bubbleSortStrings(names, n);

    printf("Sorted names: ");
    for (int i = 0; i < n; i++) {
        printf("%s ", names[i]);
    }
    printf("\n");

    return 0;
}

Output:

Total swaps: 4
Sorted names: Alice Bob Charlie Dave Eve 

Bubble sort isn’t limited to numbers. Because C strings are arrays of char, you can’t compare or assign them with > or = directly — this example uses strcmp to compare two names lexicographically and strcpy to perform the three-step swap on fixed-size char buffers. It also demonstrates instrumentation: a simple counter tracks how many swaps actually happened, a useful way to see how “close to sorted” the input already was.

How It Works Step by Step (Under the Hood)

It helps to trace one full pass by hand. Take the array [5, 1, 4, 2, 8] from Example 2 and follow the first pass (i = 0), where j runs from 0 to n - i - 2 = 3:

• j = 0: compare arr[0]=5 and arr[1]=1. 5 > 1, so swap → [1, 5, 4, 2, 8].
• j = 1: compare arr[1]=5 and arr[2]=4. 5 > 4, so swap → [1, 4, 5, 2, 8].
• j = 2: compare arr[2]=5 and arr[3]=2. 5 > 2, so swap → [1, 4, 2, 5, 8].
• j = 3: compare arr[3]=5 and arr[4]=8. 5 > 8 is false, no swap.

Notice how the value 5 kept “bubbling” rightward, losing a comparison only when it finally met something bigger (8). That’s exactly why the algorithm is called bubble sort: on every pass, the largest remaining value drifts to the right like a bubble rising to the surface. After this single pass, 8 — the true maximum — is already in its final resting place at index 4, and the next pass never touches it again, which is exactly what the shrinking bound n - i - 1 guarantees.

Internally, nothing about this needs anything more exotic than array indexing and a temporary variable. There’s no extra memory allocation, no recursion, and no hidden data structure — just repeated comparisons and swaps directly inside the original array’s memory. That simplicity is bubble sort’s main teaching value, even though it’s also why it doesn’t scale: doubling the array size roughly quadruples the number of comparisons, since the algorithm is O(n²).

Common Mistakes

Mistake 1: Swapping Without a Temporary Variable

A very common bug is trying to swap two elements without a third, temporary slot to hold one of the values. It looks harmless, but it silently destroys data:

#include <stdio.h>

int main(void) {
    int arr[] = {5, 2, 9, 1, 3};
    int n = 5;

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                arr[j] = arr[j + 1];
                arr[j + 1] = arr[j];
            }
        }
    }

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Output:

1 1 1 1 3 

The original array {5, 2, 9, 1, 3} should sort to 1 2 3 5 9, but instead most of the values collapse into duplicates and 5 and 9 vanish entirely. The problem: arr[j] = arr[j + 1] overwrites arr[j] before its original value has been saved anywhere, so the next line, arr[j + 1] = arr[j], just copies that same overwritten value back — the original is gone. The fix is to always stage one value in a temporary variable first:

#include <stdio.h>

int main(void) {
    int arr[] = {5, 2, 9, 1, 3};
    int n = 5;

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Output:

1 2 3 5 9 

With temp holding arr[j]‘s original value before anything is overwritten, both assignments now have the correct data to work with, and the array sorts correctly.

Mistake 2: Using >= Instead of > (Breaking Stability)

Bubble sort is naturally stable — elements with equal keys keep their original relative order — but only if the swap condition uses strict >. Swapping on >= too seems harmless for plain numbers, but it silently reorders equal elements, which matters when each element carries extra data:

#include <stdio.h>

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

void unstableBubbleSort(Item arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j].key >= arr[j + 1].key) {
                Item temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main(void) {
    Item arr[] = {{3, 'a'}, {1, 'b'}, {3, 'c'}, {2, 'd'}, {3, 'e'}};
    int n = 5;

    unstableBubbleSort(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%d%c ", arr[i].key, arr[i].label);
    }
    printf("\n");

    return 0;
}

Output:

1b 2d 3e 3c 3a 

The three items with key 3 started in the order a, c, e, but after sorting with >= they come out reversed as e, c, a. Swapping on equal keys keeps shuffling equal elements past each other for no sorting benefit — it just scrambles their original order. Changing the condition back to strict > fixes it:

#include <stdio.h>

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

void stableBubbleSort(Item arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j].key > arr[j + 1].key) {
                Item temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main(void) {
    Item arr[] = {{3, 'a'}, {1, 'b'}, {3, 'c'}, {2, 'd'}, {3, 'e'}};
    int n = 5;

    stableBubbleSort(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%d%c ", arr[i].key, arr[i].label);
    }
    printf("\n");

    return 0;
}

Output:

1b 2d 3a 3c 3e 

Now the equal-key items keep their original relative order (a before c before e), because equal elements are never swapped — only strictly out-of-order ones are.

Best Practices

• Always use the shrinking bound j < n - i - 1 for the inner loop, not a fixed j < n - 1; it avoids re-comparing elements that are already fixed in place and helps prevent off-by-one bugs.
• Add the “no swaps this pass” early-exit flag (Example 2). It’s a few lines of code and turns the best case into O(n), which matters if the function might ever run on nearly-sorted data.
• Always swap through a temporary variable, or a small helper function — never try to swap two values with only two assignment statements.
• Keep the comparison strictly > (or < for descending order) if you need a stable sort; only use >=/<= if you deliberately want extra swaps, which is rarely useful.
• Don’t use bubble sort for anything performance-sensitive or for large arrays (roughly n > 1000 is already noticeable). Use the standard library’s qsort, or an O(n log n) algorithm like merge sort or quicksort, for real applications.
• Treat bubble sort mainly as a teaching tool, or a fine choice for tiny, nearly-sorted datasets where its simplicity and low overhead outweigh its poor big-O.

Practice Exercises

• Exercise 1: Modify Example 1 so it sorts the array in descending order instead of ascending. (Hint: you only need to flip one comparison operator.)
• Exercise 2: Extend Example 2 so it also counts and prints the total number of comparisons made across all passes, in addition to the swap tracking it already has. For the array {5, 1, 4, 2, 8}, what’s the total?
• Exercise 3: Write a bubble sort for an array of double values that sorts them in ascending order, then prints each value with exactly two decimal places using %.2f. Test it on {3.14, 1.41, 2.72, 0.58} and confirm the output is 0.58 1.41 2.72 3.14.

Summary

• Bubble sort repeatedly compares adjacent elements and swaps them if they’re out of order, letting the largest unsorted value “bubble” to its final position on each pass.
• It needs two nested loops: the outer loop counts passes, and the inner loop’s bound n - i - 1 shrinks each pass since the tail of the array is already sorted.
• It runs in O(n²) time on average and in the worst case, but only O(1) extra space, since it sorts in place.
• Adding a swapped flag lets it exit early on already-sorted (or nearly-sorted) input, improving the best case to O(n).
• It is stable as long as the comparison uses strict > — using >= breaks stability.
• Always swap through a temporary variable; skipping it silently corrupts data instead of producing a compiler error.
• Despite its simplicity, bubble sort isn’t used in production sorting — it’s mainly a teaching tool, with qsort or an O(n log n) algorithm preferred for real work.