C: the strategy pattern with function pointers

Choose behaviour at run time by passing a function to qsort, without changing the sorting code.

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

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

static int descending(const void *x, const void *y) {
  return ascending(y, x);
}

static int by_last_digit(const void *x, const void *y) {
  int a = *(const int *)x % 10;
  int b = *(const int *)y % 10;
  return (a > b) - (a < b);
}

static void show(const char *label, const int *values, int n) {
  printf("%s:", label);
  for (int i = 0; i < n; i++) {
    printf(" %d", values[i]);
  }
  printf("\n");
}

int main(void) {
  int original[] = {42, 7, 19, 33, 8};
  int n = (int)(sizeof original / sizeof original[0]);
  int (*strategies[])(const void *, const void *) = {ascending, descending, by_last_digit};
  const char *names[] = {"ascending", "descending", "by last digit"};

  for (int s = 0; s < 3; s++) {
    int copy[5];
    for (int i = 0; i < n; i++) {
      copy[i] = original[i];
    }
    qsort(copy, (size_t)n, sizeof copy[0], strategies[s]);
    show(names[s], copy, n);
  }
  return 0;
}

ascending: 7 8 19 33 42
descending: 42 33 19 8 7
by last digit: 42 33 7 8 19

Explanation

The strategy pattern selects an algorithm at run time. In C the natural tool is a function pointer. The standard library's qsort sorts any array and asks the caller for a comparison function, so the same sorting code gives ascending, descending, or any other order depending on the strategy passed in.

A comparison function receives pointers to two elements and returns a negative number, zero, or a positive number. It must be consistent: always return the same answer for the same pair. Returning a - b is tempting but can overflow for large values, so the example uses the (a > b) - (a < b) idiom.

—

—

—

—

ascending: 7 8 19 33 42
descending: 42 33 19 8 7
by last digit: 42 33 7 8 19

Cost and common mistakes

qsort is O(n log n) comparisons on average; each comparison is O(1) here.

• The comparison function receives void pointers, so cast to the real element type before dereferencing.
• qsort is not stable: elements that compare equal may change order. Break ties explicitly if order matters.
• A comparison that is not consistent, for example one that depends on a random value, makes the result undefined.

Try it yourself

How would you sort by absolute value?

Further reading

• C reference (cppreference) (external)
• C11 committee draft (N1570) (external)
• Software Engineering at Google (external)