RadixSort.c

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <string.h>

//MacOS timespec

int numbers[800];

// Get size of statically allocated array
#define ARR_LEN(ARR) (sizeof ARR / sizeof *ARR)
// Generate random number in the interval [M,N]

static void swap(unsigned *a, unsigned *b) {
    unsigned tmp = *a;
    *a = *b;
    *b = tmp;
}

/* sort unsigned ints */
static void rad_sort_u(unsigned *from, unsigned *to, unsigned bit)
{
    if (!bit || to < from + 1) return;

    unsigned *ll = from, *rr = to - 1;
    for (;;) {
        /* find left most with bit, and right most without bit, swap */
        while (ll < rr && !(*ll & bit)) ll++;
        while (ll < rr &&  (*rr & bit)) rr--;
        if (ll >= rr) break;
        swap(ll, rr);
    }

    if (!(bit & *ll) && ll < to) ll++;
    bit >>= 1;

    rad_sort_u(from, ll, bit);
    rad_sort_u(ll, to, bit);
}

/* sort signed ints: flip highest bit, sort as unsigned, flip back */
static void radix_sort(int *a, const size_t len)
{
    size_t i;
    unsigned *x = (unsigned*) a;

    for (i = 0; i < len; i++)
            x[i] ^= INT_MIN;

        rad_sort_u(x, x + len, INT_MIN);

        for (i = 0; i < len; i++)
            x[i] ^= INT_MIN;
}

void get_numbers(char * arr) {
        FILE *file;
            file = fopen(arr, "r");
        size_t read;
        char * line = NULL;
        size_t line_len = 0;

        size_t buffer_size = 10;
        int * buffer = (int *)malloc(sizeof(int) * buffer_size);

        int seek = 0;
        while((read = getline(&line, &line_len, file)) != -1) {
            buffer[seek++] = atoi(line);

            if (seek % 10 == 0) {
                buffer_size += 10;
                buffer = (int *)realloc(buffer, sizeof(int) * buffer_size);
            }

        }

        for (int i = 0; i < seek; i++) {
                    numbers[i] = buffer[i];
            //printf("%d\n", numbers[i]);
        }
            //printf("%lu\n", ARR_LEN(numbers));
        free(buffer);
        fclose(file);
    }

  // writes the result to the output file
    void file_write(int _time, int loopN, char * str) {
        FILE *fp;
    fp = fopen(str, "a");
        //fp = NULL;
    fprintf(fp, "%d,%d\n", loopN, _time);
    fclose(fp);
    }

  // returns time to sort the list once in nanoseconds
    int _sort(int * num) {

        memset(numbers, 0, sizeof(numbers));

        struct timespec start, end;
        clock_gettime(CLOCK_MONOTONIC_RAW, &start);
        radix_sort(num, ARR_LEN(num));
        clockgettime(CLOCK_MONOTONIC_RAW, &end);
        return (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_nsec - start.tv_nsec) / 1000;
    }

int main(int argc, char *argv[])
{
    get_numbers(argv[1]);
    int * num = numbers;

    // data file:   argv[1]);
    // output file: argv[2]);
    // loops n:         argv[3]);
    for(int i = 1; i <= (int) strtol(argv[3], (char **)NULL, 10); i++) {
        file_write(_sort(num), i, argv[2]);
    }
}