Quicksort in C with unit testing framework

Question

This is my quicksort
There are many like it but
This quicksort is mine.

So, quicksort, in C, with a big framework to test it six ways from Sunday. Passed the tests nicely, but there may be warts, or subtle mistakes I didn’t think of, or code that’s hard to follow, or just better ways to do things. Have at it.

EDIT: Forgot another issue: I’m not handling memory allocation errors gracefully in this code. Suggestions on how professional-level production code might handle them are welcome. I’m thinking that functions using malloc() should return a value to be checked, and set errno to ENOMEM.

My quicksort implementation is somewhat slower than the library function; that’s only to be expected; library code is optimized and I don’t try to pick a good pivot with median-of-3 or such. No need to critique that, I wanted to keep it simple.

/* Quicksort implementation and testing framework */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* 0: use qsort correctly, to test the rest of the framework
 * 1: mess up the sort sometimes, to test if sorting errors are caught
 * 2: mess up the sentinels sometimes, to test if sentinel errors are
 * caught
 * 3: use my quicksort implementation, to test it */
#define TEST_TYPE 3
/* Stop testing after this many errors */
#define MAX_ERRORS 6
/* Set to 1 to print all pre-sort permutations */
#define VERBOSE 0
/* Max array length to test; more than 12 will take a long time */
#define MAXARRAY 10
/* Size of array for run_big_test() */
#define BIGTEST_SIZE 2000
/* Sentinels to detect buffer overruns */
#define SENTINEL_LEFT 111
#define SENTINEL_RIGHT -222
/* Used to count errors globally */
int err_ct = 0;
void run_tests(size_t N);
void run_big_test(void);
int error_check(size_t N, int *sorted);
void print_error(size_t N, int *to_sort, int *sorted);
void print_array(size_t len, int *arr);
int next_perm(int n, int *dest);
int cmp_int(const void *a, const void *b);
void quicksort(void *base, size_t nmemb, size_t size,
 int (*cmp)(const void *, const void *));
void swap(void *a, void *b, size_t size);
void memquit(void);
int main(void)
{
 size_t len;
 srand(42);
 for (len = 0; len <= MAXARRAY; ++len)
 run_tests(len);
 run_big_test();
 return EXIT_SUCCESS;
}
void run_tests(size_t N)
{
 /* Tests:
 * 1. Sort all permutations of N distinct numbers.
 * 2. Sort all permutations of N numbers with some repeated.
 * 3. Sort an array of N numbers that are all the same (may catch
 * infinite loops or recursion).
 */
 int distinct[MAXARRAY];
 int repeats[MAXARRAY] = {0, 0, 1, 2, 3, 3, 3, 4};
 int perm[MAXARRAY];
 int to_sort[MAXARRAY];
 int sorted[MAXARRAY + 2];
 int *dataset[2];
 int i;
 int test;
 int retval;
 if (N > MAXARRAY) {
 fprintf(stderr, "run_tests(%lu) exceeds max array size.\n", N);
 exit(EXIT_FAILURE);
 }
 for (i = 0; i < (int) N; ++i)
 distinct[i] = i;
 for (i = 2; i < (int) N; ++i)
 if (repeats[i] == 0)
 repeats[i] = 5;
 dataset[0] = distinct;
 dataset[1] = repeats;
 for (test = 0; test < 2; ++test) {
 while ((retval = next_perm((int) N, perm)) == 1) {
 for (i = 0; i < (int) N; ++i)
 to_sort[i] = dataset[test][perm[i]];
#if VERBOSE
 print_array(N, to_sort);
 putchar('\n');
#endif
 sorted[0] = SENTINEL_LEFT;
 memcpy(sorted + 1, to_sort, N * sizeof(int));
 sorted[N + 1] = SENTINEL_RIGHT;
 quicksort(sorted + 1, (size_t) N, sizeof(int), cmp_int);
 if (error_check(N, sorted))
 print_error(N, to_sort, sorted);
 }
 if (retval == -1)
 memquit();
 }
 for (i = 0; i < (int) N; ++i)
 to_sort[i] = 6;
#if VERBOSE
 print_array(N, to_sort);
 putchar('\n');
#endif
 sorted[0] = SENTINEL_LEFT;
 memcpy(sorted + 1, to_sort, N * sizeof(int));
 sorted[N + 1] = SENTINEL_RIGHT;
 quicksort(sorted + 1, (size_t) N, sizeof(int), cmp_int);
 if (sorted[0] != SENTINEL_LEFT ||
 sorted[N + 1] != SENTINEL_RIGHT ||
 memcmp(sorted + 1, to_sort, N * sizeof(int)))
 print_error(N, to_sort, sorted);
}
void run_big_test(void)
{
 /* Create a long array of random numbers, sort it, check
 * correctness. */
 int *to_sort;
 int *sorted;
 int i;
 to_sort = malloc(BIGTEST_SIZE * sizeof(int));
 sorted = malloc((BIGTEST_SIZE + 2) * sizeof(int));
 if (!to_sort || !sorted)
 memquit();
 for (i = 0; i < BIGTEST_SIZE; ++i)
 to_sort[i] = rand() % (BIGTEST_SIZE * 4);
#if VERBOSE
 print_array(BIGTEST_SIZE, to_sort);
 putchar('\n');
#endif
 sorted[0] = SENTINEL_LEFT;
 memcpy(sorted + 1, to_sort, BIGTEST_SIZE * sizeof(int));
 sorted[BIGTEST_SIZE + 1] = SENTINEL_RIGHT;
 quicksort(sorted + 1, BIGTEST_SIZE, sizeof(int), cmp_int);
 if (error_check(BIGTEST_SIZE, sorted))
 print_error(BIGTEST_SIZE, to_sort, sorted);
}
int error_check(size_t N, int *sorted)
{
 /* Check sentinels, check that sorted part is non-decreasing */
 size_t i;
 if (sorted[0] != SENTINEL_LEFT ||
 sorted[N + 1] != SENTINEL_RIGHT)
 return 1;
 for (i = 2; i <= N; ++i)
 if (sorted[i] < sorted[i - 1])
 return 1;
 return 0;
}
void print_error(size_t N, int *to_sort, int *sorted)
{
 /* Print pre-sort and post-sort arrays to show where error occurred.
 * Quit if MAX_ERRORS was reached. */
 printf("Error: ");
 print_array(N, to_sort);
 printf(" -> ");
 print_array(N + 2, sorted);
 putchar('\n');
 if (++err_ct >= MAX_ERRORS)
 exit(EXIT_FAILURE);
}
void print_array(size_t len, int *arr)
{
 /* Pretty-print array. No newline at end. */
 char *sep = "";
 size_t i;
 putchar('(');
 for (i = 0; i < len; ++i) {
 printf("%s%d", sep, arr[i]);
 sep = ", ";
 }
 putchar(')');
}
int next_perm(int passed_n, int *dest)
{
 /* Generate permutations of [0, n) in lexicographic order.
 *
 * First call: Set up, generate first permutation, return 1.
 *
 * Subsequent calls: If possible, generate next permutation and
 * return 1. If all permutations have been returned, clean up and
 * return 0. "First call" status is reset and another series may be
 * generated.
 *
 * Return -1 to indicate a memory allocation failure.
 *
 * Caller may alter the values in `dest` freely between calls, and
 * may pass a different `dest` address each time. `n` is ignored
 * after the first call.
 *
 * The function maintains static data; it can only keep track of one
 * series of permutations at a time. */
 static int *perm;
 static int new_series = 1;
 static int n;
 int i, j;
 if (new_series) {
 /* Set up first permutation, return it. */
 new_series = 0;
 n = passed_n;
 if ((perm = malloc((size_t) n * sizeof(int))) == NULL)
 return -1;
 for (i = 0; i < n; ++i)
 perm[i] = dest[i] = i;
 return 1;
 }
 /* Generate and return next permutation. First, find longest
 * descending run on right. */
 i = n - 2;
 while (i >= 0 && perm[i] > perm[i+1])
 --i;
 /* If all of perm is descending, the previous call returned the last
 * permutation. */
 if (i < 0) {
 free(perm);
 new_series = 1;
 return 0;
 }
 /* Find smallest value > perm[i] in descending run. */
 j = n - 1;
 while (perm[j] < perm[i])
 --j;
 /* Swap [i] and [j]; run will still be descending. */
 perm[i] ^= perm[j];
 perm[j] ^= perm[i];
 perm[i] ^= perm[j];
 /* Reverse the run, and we're done. */
 for (++i, j = n - 1; i < j; ++i, --j) {
 perm[i] ^= perm[j];
 perm[j] ^= perm[i];
 perm[i] ^= perm[j];
 }
 for (i = 0; i < n; ++i)
 dest[i] = perm[i];
 return 1;
}
int cmp_int(const void *a, const void *b)
{
 /* Compatible with qsort. a and b are treated as pointers to int.
 * Return value is:
 * < 0 if *a < *b
 * > 0 if *a > *b
 * 0 if *a == *b
 */
 const int *aa = a;
 const int *bb = b;
 return *aa - *bb;
}
#if TEST_TYPE == 0
/* Use qsort(3), correctly */
void quicksort(void *base, size_t nmemb, size_t size,
 int (*cmp)(const void *, const void *))
{
 qsort(base, nmemb, size, cmp);
}
#endif
#if TEST_TYPE == 1
/* Mess up the sort with probability 1/256 */
void quicksort(void *base, size_t nmemb, size_t size,
 int (*cmp)(const void *, const void *))
{
 int *ibase = base;
 qsort(base, nmemb, size, cmp);
 if (rand() % 256 == 0) {
 ibase[0] ^= ibase[nmemb - 1];
 ibase[nmemb - 1] ^= ibase[0];
 ibase[0] ^= ibase[nmemb - 1];
 }
}
#endif
#if TEST_TYPE == 2
/* Mess up one of the sentinels with probability 1/256 */
void quicksort(void *base, size_t nmemb, size_t size,
 int (*cmp)(const void *, const void *))
{
 int *ibase = base;
 int i;
 qsort(base, nmemb, size, cmp);
 if (rand() % 256 == 0) {
 i = (rand() % 2) ? -1 : (int) nmemb;
 ibase[i] = 42;
 }
}
#endif
#if TEST_TYPE == 3
/* Use my implementation */
void quicksort(void *base, size_t nmemb, size_t size,
 int (*cmp)(const void *, const void *))
{
 /* Sort array with quicksort algorithm. Pivot is always leftmost
 * element. */
 char *cbase = base;
 char *p, *q;
 if (nmemb < 2)
 return;
 /* p at element 1, just past pivot */
 p = cbase + size;
 /* q at last element */
 q = cbase + (nmemb - 1) * size;
 while (p <= q) {
 /* Move p right until *p >= pivot */
 while (p <= q && cmp(p, base) < 0)
 p += size;
 /* Move q left until *q < pivot */
 while (p <= q && cmp(q, base) >= 0)
 q -= size;
 if (p < q)
 swap(p, q, size);
 }
 /* After partitioning:
 * Pivot is element 0
 * p = q + 1 (in terms of elements)
 * Case 1: some elements < pivot, some >= pivot
 * =<<<<>>>> q is rightmost <, p is leftmost >
 * Case 2: all elements < pivot
 * =<<<<<<<< q is rightmost <, p is one past end
 * Case 3: all elements >= pivot
 * =>>>>>>>> q is =, p is leftmost >
 * 
 * If not case 3:
 * Swap pivot with q
 * Recurse on 0 to q - 1
 * Recurse on p to nmemb - 1
 *
 * Pivot is left out of both recursive calls, so size is always
 * reduced by at least one and infinite recursion cannot occur.
 */
 if (q != cbase) {
 swap(base, q, size);
 quicksort(base, (size_t) (q - cbase) / size, size, cmp);
 }
 quicksort(p, nmemb - (size_t) (p - cbase) / size, size, cmp);
}
#endif
void swap(void *a, void *b, size_t size)
{
 static size_t bufsize = 0;
 static char *buf = NULL;
 if (size != bufsize) {
 bufsize = size;
 buf = realloc(buf, bufsize);
 if (!buf)
 memquit();
 }
 memcpy(buf, a, size);
 memcpy(a, b, size);
 memcpy(b, buf, size);
}
void memquit(void)
{
 fprintf(stderr, "Memory allocation failure\n");
 exit(EXIT_FAILURE);
}

• Tom Zych: Oh yay, I won a Tumbleweed! :p

Answer 1

#define TEST_TYPE 3

It would be more informative to represent this as an enum, with meaningfully named entries for your four test types.

/* Set to 1 to print all pre-sort permutations */
#define VERBOSE 0

No reason not to represent this as an actual boolean using <stdbool.h>.

Since it seems like this is the only translation unit in your project, you should set all of your functions to be static.

Don't pre-declare your variables at the beginning of a function; this hasn't been needed for about 20 years. e.g. rewrite your main loop as:

for (size_t len = 0; len <= MAXARRAY; len++)

This especially applies to functions like run_tests, with a big pile of variables at the beginning.

In run_big_test, you should be freeing to_sort and sorted after you're done with them.

This:

i = n - 2;
while (i >= 0 && perm[i] > perm[i+1])
 --i;

is better represented as a for loop:

for (int i = n-2; i >= 0; i--) 
 if (perm[i] <= perm[i+1])
 break;

I suggest that you factor out your XOR swap into a function. The compiler will be smart enough to inline it.

• Tom Zych: Thanks for all of this. Regarding pre-declarations, I’ve been using -ansi with gcc to force me to write maximally-compatible C code. Is that not really an issue these days?
• Reinderien: You really should assume everyone has C99 or newer.