1
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ Oh yay, I won a Tumbleweed! :p \$\endgroup\$ – Tom Zych Dec 24 '18 at 11:13
1
\$\begingroup\$
#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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Tom Zych Dec 28 '18 at 23:22
  • \$\begingroup\$ You really should assume everyone has C99 or newer. \$\endgroup\$ – Reinderien Dec 28 '18 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.