C Bubble Sort

Walk the array; swap adjacent pairs that are out of order. Repeat until no swaps. O(n²) — slow, but simplest sort to understand.

Bubble sort is the entry-level sorting algorithm. Worst possible big-O for sorting (tied with selection and insertion), but its simplicity makes it the standard pedagogical example.

The basic shape

#include <stdio.h>

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

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

  bubble_sort(nums, n);

  for (int i = 0; i < n; i++) printf("%d ", nums[i]);
  printf("\n");
  // 11 12 22 25 64
}

How it works

Imagine bubbles rising. In each pass, the largest unsorted element bubbles to the right.

Pass 1 on [64, 25, 12, 22, 11]:

• Compare 64, 25 → swap → [25, 64, 12, 22, 11]
• Compare 64, 12 → swap → [25, 12, 64, 22, 11]
• Compare 64, 22 → swap → [25, 12, 22, 64, 11]
• Compare 64, 11 → swap → [25, 12, 22, 11, 64]

After pass 1, 64 is at the end (its final position).

Pass 2 on [25, 12, 22, 11, _64_] (only first 4 need checking):

• Compare 25, 12 → swap → [12, 25, 22, 11, 64]
• Compare 25, 22 → swap → [12, 22, 25, 11, 64]
• Compare 25, 11 → swap → [12, 22, 11, 25, 64]

After pass 2, 25 is in place.

And so on, until everything's sorted.

The inner loop bound

for (int j = 0; j < n - 1 - i; j++)

The - i is the optimization: after pass i, the last i elements are already in place, so we don't re-check them.

Without that, you'd compare elements that are already known sorted — wasted work but not incorrect.

Swap

int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;

Three assignments. Standard "swap two values via temporary."

For a function:

void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

Pointers required because C passes by value. Episode 19 covered this.

Optimised: stop early if sorted

void bubble_sort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    int swapped = 0;
    for (int j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = 1;
      }
    }
    if (!swapped) break;   // nothing to swap = already sorted
  }
}

If a pass made no swaps, the array is sorted — exit early. Best case: already sorted → one pass → O(n).

Complexity

For 1,000 elements: ~500,000 comparisons. For 1,000,000: ~500 billion. Bubble sort is unusable on real data.

Why teach it

• Conceptually simple. Two loops, one comparison, one swap.
• In-place. No extra memory.
• Stable. Equal elements maintain relative order.
• Adaptive. Best case is O(n) with early exit.

But the O(n²) average makes it useless for production. Use:

• Quicksort — O(n log n) average, in-place.
• Mergesort — O(n log n) worst case, stable, but O(n) extra memory.
• Heapsort — O(n log n) worst case, in-place.
• Insertion sort — O(n²) worst, but very fast on small or near-sorted arrays.

Episode 54 covers mergesort; episode 55 quicksort.

qsort: the stdlib answer

#include <stdlib.h>

int compare_ints(const void *a, const void *b) {
  return (*(int *)a) - (*(int *)b);
}

int nums[] = {64, 25, 12, 22, 11};
qsort(nums, 5, sizeof(int), compare_ints);

C's stdlib provides qsort — typically a quicksort (sometimes introsort). For real code, just use this. Bubble sort is for learning.

Stability

A "stable" sort preserves the relative order of equal elements. Useful when items are sorted by a key but you want the original order among ties.

Bubble sort is stable: we only swap when arr[j] > arr[j+1] (strict greater). Equal elements stay put.

Quicksort, by contrast, is not stable in its standard form.

Common mistakes

<= instead of < in swap condition. arr[j] > arr[j+1] keeps stability. arr[j] >= arr[j+1] swaps equals — not necessarily wrong but breaks stability.

Wrong loop bounds. j < n - 1 - i — the -1 accounts for "comparing j with j+1" (don't index past the end). The -i is the optimization.

Sorting wrong direction. Want descending? arr[j] < arr[j+1] flips it.

Missing the optimization. Without - i or early-exit, bubble sort always runs full n² iterations regardless of input.

Sorting in main with global array. Test from a function — passes the array to be sorted. Globals make testing harder.

What's next

Episode 54: merge sort. O(n log n) divide and conquer. Stable; uses extra memory.

Recap

Bubble sort: walk array, swap adjacent out-of-order pairs, repeat until done. O(n²) worst case. Optimization: track swapped flag for early exit on sorted input. In-place, stable, adaptive — but slow. Use qsort from stdlib for real work; bubble sort is for understanding the basic shape of "compare and swap" sorting.

Next episode: merge sort.