C string radixsort

msd_radix_string_sort.c

#include "library.h"

#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
// #include <conio.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

int radix_sort_string(char **strings, char **copy_strings, size_t lo, size_t hi, size_t pos, size_t string_ptr_offset)
{
    // size_t maxlen;
    //    unsigned int c;

//    printf("starting to sort position %d from %d to %d\n", pos, lo, hi);
    size_t s;
//    for (s = lo; s < hi; s++)
//    {
//         printf("%s\n", strings[s]+string_ptr_offset);
//    }

    // pointer to counter
    size_t bins[256];

    for (int j = 0; j < 256; j++)
    {
        bins[j] = 0;
    }

    // count the number occurences of each byte

    for (size_t j = lo; j < hi; j++)
    {
        size_t ci = 0;
        if (strlen(strings[j]+string_ptr_offset) >= pos)
        {
            ci = (strings[j]+string_ptr_offset)[pos];
        }
        bins[ci]++;
    }

    // compute the cumulative sum that represents the correct location
    for (size_t j = 1; j < 256; j++)
    {
        bins[j] = bins[j - 1] + bins[j];
    }

    // make a copy for easy recursion later
    size_t copy_bins[256];
    for (int i = 0; i < 256; ++i)
    {
        copy_bins[i] = bins[i] + lo;
    }

    for (int j = 255; j >= 1; j--)
    {
        bins[j] = bins[j - 1] + lo;
    }
    bins[0] = lo;

    // now go through the strings again and place them in the right order
    for (size_t i = lo; i < hi; i++)
    {
        size_t ci = 0;
        if (strlen(strings[i]+string_ptr_offset) >= pos)
        {
            ci = (strings[i]+string_ptr_offset)[pos];
        }
        copy_strings[bins[ci]] = strings[i];
        bins[ci]++;
    }

//     printf("after sorting position: %d\n", pos);
    for (s = lo; s < hi; s++)
    {
        strings[s] = copy_strings[s];
//         printf("%s\n", strings[s]+string_ptr_offset);
    }

    for (int i = 1; i < 256; i++)
    {
        if (copy_bins[i] - copy_bins[i - 1] > 1)
        {
            // printf("%d %d\n", copy_bins[i-1], copy_bins[i]);
            // for (int j = copy_bins[i-1]; j < copy_bins[i]; j++) {
            // 	strings[j] = copy_strings[j];
            // }
            // free(bins);
            lo = copy_bins[i - 1];
            hi = copy_bins[i];
            // free(copy_bins);
            radix_sort_string(strings, copy_strings, lo, hi, pos + 1, string_ptr_offset);
            // return 0;
        }
    }

    return 0;
}

void radix_sort(char **strings, size_t len) {
//    const size_t len = sizeof(strings) / sizeof(char *);
//    printf("length of input array is %d and pointer is %d\n", len, sizeof(char**));
//    strings[0] = strings[len-1];
    size_t s;
    const size_t string_ptr_offset = 8;
//    for (s = 0; s < len; s++)  {
//        printf("%s\n", strings[s]+string_ptr_offset);
//    }

//    char *copy_strings[len];
    char **copy_strings = malloc(sizeof(char*) * len);
    printf("finished copying string1");
    for (s = 0; s < len; s++) {
        copy_strings[s] = strings[s];
    }
//    printf("finished copying string2");

    // compute the length of strings once
//    size_t strlens[len];
//    for (size_t i = 0; i < len; ++i) {
//        strlens[i] = strlen(strings[i]+8);
//    }
//    printf("finished copying string");

    radix_sort_string(strings, copy_strings, 0, len, 0, string_ptr_offset);

    return;
}