shotgun.c

/*
    shotgun.c
    Author: George Lesica <glesica@gmail.com>
    Description: An ANSI C implementation of the shotgun sorting algorithm.
*/

#include <stdlib.h>

/* Private utility functions. */

int sorted(
    const void *base,
    size_t num,
    size_t size,
    int (*comparator) (const void *, const void *)
) {
    int i;

    char *b = (char *) base;

    for (i=1; i<num; i++) {
        if (comparator(&b[(i-1)*size], &b[i*size]) > 0) {
            return 0;
        }
    }
    return 1;
}

void randomize(
    void *base,
    size_t num,
    size_t size
) {
    int i, j;
    char *b = (char *) base;
    void *temp = malloc(size);

    for (i=0; i<num; i++) {
        j = rand() % num;
        memcpy(temp, &b[i*size], size);
        memcpy(&b[i*size], &b[j*size], size);
        memcpy(&b[j*size], temp, size);
    }

    free(temp);
}

/* Public Functions */

int int_compare(void *a, void *b) {
    return (*(int *) a - *(int *) b);
}

void sgsort(
    void *base, 
    size_t num, 
    size_t size, 
    int (*comparator) (const void *, const void *)
) {
    /* Loop until the array is sorted */
    while (! sorted(base, num, size, comparator)) {
        randomize(base, num, size);
    }

}

/* Testing */

int main() {
/*
    int test[5];
    sgsort(test, 5);
    
    int i;
    for (i=0; i<5; i++) {
        printf("%d ", test[i]);
    }
    printf("\n");
*/
}