Algorithms

Linked Lists

A node of a singly linked list.

struct Node {
    int          data;
    struct Node *next;
};

Insertion at the head.

struct Node *push(struct Node *head, int v) {
    struct Node *n = malloc(sizeof *n);
    n->data = v;
    n->next = head;
    return n;
}

Search

Linear search.

int linear_search(const int *xs, size_t n, int target) {
    for (size_t i = 0; i < n; i++)
        if (xs[i] == target) return (int)i;
    return -1;
}

Binary search on a sorted array.

int binary_search(const int *xs, size_t n, int target) {
    size_t lo = 0, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if      (xs[mid] == target) return (int)mid;
        else if (xs[mid] <  target) lo = mid + 1;
        else                        hi = mid;
    }
    return -1;
}

Sorting

Insertion sort, short, in-place, stable.

void insertion_sort(int *xs, size_t n) {
    for (size_t i = 1; i < n; i++) {
        int   key = xs[i];
        size_t j  = i;
        while (j > 0 && xs[j - 1] > key) {
            xs[j] = xs[j - 1];
            j--;
        }
        xs[j] = key;
    }
}

For larger inputs, qsort from <stdlib.h> is usually the right answer:

int cmp_int(const void *a, const void *b) {
    int x = *(const int *)a, y = *(const int *)b;
    return (x > y) - (x < y);
}

qsort(xs, n, sizeof *xs, cmp_int);