qsort seems to change values

Question

I'm stuck with following problem:

int sort_compare(const void *x, const void *y) {
    const int *xi = *(const int **) x;
    const int *yi = *(const int **) y;

    for (int i = 0; i < block_size; i++) {
        comp_x[i] = block[(*xi + i) % block_size];
        comp_y[i] = block[(*yi + i) % block_size];
    }

    return memcmp(comp_x, comp_y, block_size);
}

void sort() {
    for (int i = 0; i < block_size; i++) {
        printf("%d,", to_sort[i]);
    }
    puts("");
    qsort(to_sort, block_size, sizeof (int), sort_compare);
    for (int i = 0; i < block_size; i++) {
        printf("%d,", to_sort[i]);
    }
    puts("");
}

values:
    block_size = 5;
    block = "jkldj";
    comp_x, compy_y and to_sort are well allocated

output:
    0,1,2,3,4,
    3,0,1785357420,1,1684826986,

to_sort contains the first letter from a (circular) string e.g.

qwer
werq
erqw
rqwe

, represented as (0,1,2,3) needs to be sorted to

erqw
rqwe
qwer
werq

, represented as (2,3,0,1). I seem to get very large numbers, why is that?

Thanks in advance!

Answer 1

The x and y passed into your comparator are pointers to your array elements. Your array elements are ints, so to get the int values, you need to cast the void pointers into int pointers and dereference. You have an extra layer of indirection in your code, it should really look like this:

int xi = *(const int *) x;
int yi = *(const int *) y;

Then just use xi and yi directly instead of *xi and *yi when doing the data comparison.

As an optimization, there's no need to copy the data into separate arrays and then memcmp them -- you can just compare them yourself in the loop:

for (int i = 0; i < block_size; i++) {
    char data_x = block[(xi + i) % block_size];
    char data_y = block[(yi + i) % block_size];
    if (data_x != data_y)
        return data_x - data_y;
}

return 0;

And as a further optimization, if you double the data in the block array (e.g. so that it has "qwerqwer" instead of just "qwer"), you can do the comparison in a single call to memcmp, since you no longer have to deal with the wraparound. memcmp is heavily optimized, so if you have a lot of data, it can be much faster to use memcmp then a hand-written for loop.