Algorithms

Complexity — The Language of Cost

Big-O notation describes how an algorithm's work grows with input size n. An O(n) algorithm does ~n steps for n items; O(n²) does ~n². Doubling n doubles an O(n) run but quadruples an O(n²) run — which is why choosing the right algorithm matters more than any constant factor, especially in C where the data can be huge.

Sorting

Before you ever implement a sort, know this: production C calls qsort from the standard library. The algorithms below exist so you understand what qsort does internally and how to reason about it.

Bubble Sort — The Teaching Algorithm

Bubble sort repeatedly walks the array, swapping adjacent pairs that are out of order, until one complete pass makes no swaps. Simple, correct, and O(n²) — fine for 100 items, a disaster for a million. Its only virtue is that it is easy to prove correct.

#include <stdio.h>

// bubble sort: n-1 passes; each pass bubbles the largest remaining value right
void bubble_sort(int a[], size_t n) {
    for (size_t pass = 0; pass < n - 1; pass++) {
        int swapped = 0;                       // early exit when already sorted
        for (size_t i = 0; i < n - 1 - pass; i++) {   // the sorted tail shrinks
            if (a[i] > a[i + 1]) {             // adjacent pair out of order?
                int tmp = a[i];                // swap them
                a[i] = a[i + 1];
                a[i + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break;                   // no swap: the array is sorted
    }
}

int main(void) {
    int a[] = {5, 2, 9, 1, 7};
    size_t n = sizeof(a) / sizeof(a[0]);
    bubble_sort(a, n);
    for (size_t i = 0; i < n; i++) printf("%d ", a[i]);   // 1 2 5 7 9
    printf("\n");
    return 0;
}

Quicksort — Divide and Conquer

Quicksort picks a pivot, partitions the array so smaller values sit left and larger right, then recurses on both sides. Average O(n log n) and excellent cache behavior make it the default sort of most libraries. Worst case is O(n²) when the pivots are pathological — hence production variants pick pivots carefully.

#include <stdio.h>

// partition: rearrange [lo..hi] around a pivot, return pivot's final index
static size_t partition(int a[], size_t lo, size_t hi) {
    int pivot = a[hi];               // simple choice: last element
    size_t i = lo;                   // the boundary of "smaller than pivot"
    for (size_t j = lo; j < hi; j++) {
        if (a[j] < pivot) {          // found a smaller element: move it left
            int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
            i++;
        }
    }
    int tmp = a[i]; a[i] = a[hi]; a[hi] = tmp;   // pivot to its sorted slot
    return i;
}

static void qs(int a[], size_t lo, size_t hi) {
    if (lo >= hi) return;            // base case: zero or one element
    size_t p = partition(a, lo, hi);
    if (p > lo) qs(a, lo, p - 1);    // sort the left side (guard underflow)
    qs(a, p + 1, hi);                // sort the right side
}

int main(void) {
    int a[] = {9, 3, 7, 1, 8, 2};
    size_t n = sizeof(a) / sizeof(a[0]);
    qs(a, 0, n - 1);
    for (size_t i = 0; i < n; i++) printf("%d ", a[i]);   // 1 2 3 7 8 9
    printf("\n");
    return 0;
}

qsort — The Library Sort

The standard qsort is generic: you hand it the array, its count, its element size, and a comparator function pointer — the callback pattern that powers C's late binding (more on callbacks in advanced C).

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

// comparator contract: negative if a<b, zero if equal, positive if a>b
static int cmp_int(const void *a, const void *b) {
    int x = *(const int *)a;         // void* is blind — cast to int*
    int y = *(const int *)b;
    return (x > y) - (x < y);        // portable subtraction that cannot overflow
}

int main(void) {
    int a[] = {42, 7, 3, 99, 1};
    size_t n = sizeof(a) / sizeof(a[0]);
    qsort(a, n, sizeof(int), cmp_int);
    for (size_t i = 0; i < n; i++) printf("%d ", a[i]);   // 1 3 7 42 99
    printf("\n");
    return 0;
}

Searching

Linear search scans from the start — O(n), the only option on unordered data. Binary search halves the range each step — O(log n) — but requires the array to be sorted first. The price of the fast search is the sort that precedes it.

#include <stdio.h>

// binary search: return index of target or -1; array must be sorted
long binary_search(const int a[], size_t n, int target) {
    size_t lo = 0, hi = n;            // half-open range [lo, hi)
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;   // overflow-safe midpoint
        if (a[mid] == target) return (long)mid;
        if (a[mid] < target) lo = mid + 1; // answer is to the right
        else                 hi = mid;     // answer is to the left
    }
    return -1;                        // range collapsed: not present
}

int main(void) {
    int a[] = {2, 4, 6, 8, 10, 12};
    long at = binary_search(a, 6, 8);
    printf("8 is at index %ld\n", at);        // 3
    printf("7 gives %ld\n", binary_search(a, 6, 7));   // -1
    return 0;
}

Recursion & Memoization

Recomputing the same subproblems is the classic hidden cost of naive recursion. The naive Fibonacci below calls itself exponentially — fib(40) performs ~2⁴⁰ calls. Memoization stores each answer once, collapsing the cost to O(n). This is the difference between a slow toy and an algorithm.

#include <stdio.h>

// naive: exponential — it recomputes the same subtree countless times
unsigned long fib_slow(unsigned int n) {
    if (n < 2) return n;
    return fib_slow(n - 1) + fib_slow(n - 2);
}

// memoized: each value is computed once, then reused — O(n)
unsigned long fib_fast(unsigned int n) {
    static unsigned long memo[100] = {0, 1};    // static: survives calls
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];           // already known? reuse it
    memo[n] = fib_fast(n - 1) + fib_fast(n - 2); // compute once, store
    return memo[n];
}

int main(void) {
    printf("fib_fast(40) = %lu\n", fib_fast(40));   //  102334155, instantly
    // printf("fib_slow(40) would take seconds...");  // the exponential version
    return 0;
}

Dynamic programming is exactly this idea generalized: solve each subproblem once, in order, and combine. Memoization is its top-down form.

The Sieve of Eratosthenes

A beautiful example of space-time trade: to find all primes up to n, mark multiples of every prime as composite. Each composite is crossed out once, so the total work is O(n log log n) — the fastest known way to list primes, and a genuine "interesting algorithm" that rewards thinking about loops, arrays, and index math.

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

// list all primes <= limit using a boolean sieve
void sieve(unsigned int limit) {
    bool *composite = calloc(limit + 1, sizeof(bool));   // all false = prime so far
    if (composite == NULL) return;
    for (unsigned int p = 2; p * p <= limit; p++) {      // only need p up to sqrt
        if (!composite[p]) {                             // p is still prime
            for (unsigned int m = p * p; m <= limit; m += p)
                composite[m] = true;                     // mark multiples
        }
    }
    for (unsigned int i = 2; i <= limit; i++)
        if (!composite[i]) printf("%u ", i);
    printf("\n");
    free(composite);
}

int main(void) {
    sieve(30);    // 2 3 5 7 11 13 17 19 23 29
    return 0;
}

Note the two micro-optimizations that keep it fast: marking starts at p*p (smaller multiples were already marked) and the outer loop stops at the square root. Small index thoughts, big speedup.

Keep Practicing

The reference implementation of every classic algorithm — including mergesort, heapsort, k-d trees, and dynamic programming — is documented in C in the open-source collection TheAlgorithms/C. Read one file a day, rebuild it adding a test, and your algorithmic eye will sharpen fast.

Next: advanced C — callbacks, bit tricks, and type punning.