c sort

[KevinACoder]

void bucket_sort_fvec(fvector *v, float_cmp_ptr cmp);

void radix_sort_vec(vector *v);

static void fswap(float *lhs, float *rhs) {
    float tmp = *lhs;
    *lhs = *rhs;
    *lhs = tmp;
}

void bucket_sort_fvec(fvector *v, float_cmp_ptr cmp) {
    //create buckets for count sorting
    const int BUCKET_NUM = 10;
    fvector buckets[BUCKET_NUM];
    for (int i = 0; i < BUCKET_NUM; i++) {
        init_fvec(&buckets[i]);
    }

    //put all elements into bukcets
    int ix = 0;
    for (int i = 0; i < v->len; i++) {
        ix = v->items[i] * BUCKET_NUM;
        if (ix < 0 || ix > BUCKET_NUM)
            err_exit(BAD_INDEX);
        push_back_fvec(&buckets[ix], v->items[i]);
    }

    //sort each buckets
    for (int i = 0; i < BUCKET_NUM; i++) {
        select_sort_fvec(&buckets[ix], cmp);
    }

    //merge all buckets
    ix = 0;
    for (int i = 0; i < BUCKET_NUM; i++) {
        for (int j = 0; j < buckets[i].len; j++) {
            v->items[ix++] = buckets[i].items[j];
        }
    }
}

int get_max_ele(vector *v) {
    int mx = INT_MIN;
    for (int i = 0; i < v->total; i++) {
        if (mx < (int)v->items[i])
            mx = (int)v->items[i];
    }
    return mx;
}

#define GET_DIGIT(a, n) ((a)/n)%10  

//sort arry according to the digit represented by exp
void count_sort(vector *v, int exp) {
    int bucket_num = 10;
    int *output = calloc(v->total, sizeof(int)),  //output array
        *count = calloc(bucket_num, sizeof(int));

    //store the count of occurences
    for (int i = 0; i < v->total; i++)
        count[GET_DIGIT(VECTOR_GET(*v, int, i), exp)]++;

    //make count[i] contain the actual position of this digit
    // in output
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    //build the output array
    for (int i = v->total - 1; i >= 0; i--) {
        int digit = GET_DIGIT(VECTOR_GET(*v, int, i), exp);
        output[digit - 1] = (int)v->items[i];
        count[digit]--;
    }

    //copy ouput array to dst
    for (int i = 0; i < v->total; i++)
        v->items[i] = (void *)(long)output[i];

    free(output);
    free(count);
}

void radix_sort_vec(vector *v) {
    int mx = get_max_ele(v);

    //start sorting from less significant digit
    for (int exp = 1; mx / exp > 0; exp *= 10)
        count_sort(v, exp);
}

void test_sort() {
    int nums[] = { 4, 2, 3, 1 , 7, 5, 6};
    VECTOR_INIT(arr);
    VECTOR_SET_DATA(arr, nums, ITEM_OF(nums));
    VECTOR_PRINT(arr);
    //shell_sort_vec(&arr, less_cmp);
    //heap_sort_vec(&arr, true);
    radix_sort_vec(&arr);
    VECTOR_PRINT(arr);

    VECTOR_RESET(arr);

    float fnums[] = {0.45, 0.23, 0.44, 0.26, 0.78, 0.12};
    fvector farr;
    init_fvec(&farr);
    set_data_fvec(&farr, fnums, ITEM_OF(fnums));
    print_fvec(&farr);
    bucket_sort_fvec(&farr, less_cmp_f);
    print_fvec(&farr);
    reset_fvec(&farr);
}