Krdytkyu

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.

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 failuren");

    exit(EXIT_FAILURE);

}