Quick Sort in C

Question

I'd like to know if there's any issues with this implementation of qsort_r (which is not available in all implementations, so I'm trying to provide one that allows to compare values in a dynamic environment) and whether it could be improved upon.

typedef int32_t compare_fn(void *data, const void *val1, const void *val2);
void memswap(void *mem1, void *mem2, size_t size)
{
 uint8_t buffer[size];
 memcpy(buffer, mem1, size);
 memcpy(mem1, mem2, size);
 memcpy(mem2, buffer, size);
}
void qsort_r(void *mem_low, void *mem_hi, size_t size, compare_fn compare, void *data)
{
 if (mem_low >= mem_hi || mem_hi < mem_low)
 {
 return;
 }
 uint8_t *mem_i = mem_low;
 uint8_t *mem_j = mem_low;
 while (mem_j < mem_hi)
 {
 if (compare(data, mem_j, mem_hi) < 0)
 {
 memswap(mem_i, mem_j, size);
 mem_i += size;
 }
 mem_j += size;
 }
 memswap(mem_i, mem_hi, size);
 qsort_r(mem_low, mem_i - size, size, compare, data);
 qsort_r(mem_i + size, mem_hi, size, compare, data);
}

• Sᴀᴍ Onᴇᴌᴀ: Please see What to do when someone answers. I have rolled back Rev 4 → 2

Answer 1

1. Pointer-arithmetic on void* is an error in standard c. Yes, gcc/clang have an extension assuming that sizeof(void) == 1. Ramp up your warning-level and specify the standard.

2. That's an interesting method to swap two blocks of memory.

   Using a variable length array invites undefined behavior though, as the amount of stack requested is pretty much unbounded.

   Anyway, it would probably be a good idea to implement it directly, without such a buffer.

   void memswap(void* a, void* b, size_t n) {
    unsigned char *c = a, *d = b;
    while (n--) {
    unsigned char x = *c;
    *c++ = *d;
    *d++ = x;
    }
   }
   

3. I somewhat expected all the elements to be between mem_low and mem_hi. You seem to have an element at mem_hi.
   At least if you sort a null terminated string, it just sorts the terminator too.

Did you try to run your code? See it break a basic test-case live on coliru.

• Jazzwave06: I had tried it on an integer array of 10k elements, but it hid a nasty bug. My pivot cannot be mem_hi, it must be mem_hi - size. This change will solve (1). As for (2), it is very interesting, would there be a performance difference? I'll update the code with the changes.

Answer 2

if (mem_low >= mem_hi || mem_hi < mem_low)

The second part of that if is completely redundant.