Что случилось с моей обычной сортировкой?

Question

Я пытаюсь написать общий быстрой сортировки:

void _qsort(void *ptr, 
     size_t lrange, 
     size_t rrange, 
     size_t size, 
     int (*cmp)(const void *, const void *)) 
{ 
    if (lrange < rrange) { 
     size_t i, j; 
     void *key; 

     key = malloc(size); 
     i = lrange; 
     j = rrange; 
     memcpy(key, ptr + i * size, size); 
     while (i < j) { 
      while (i < j && (*cmp)(ptr + j * size, key) > 0) 
       j--; 
      if (i < j) { 
       memcpy(ptr + i * size, ptr + j * size, size); 
       i++; 
      } 
      while (i < j && (*cmp)(key, ptr + i * size) > 0) 
       i++; 
      if (i < j) { 
       memcpy(ptr + j * size, ptr + i * size, size); 
       j--; 
      } 
     } 
     memcpy(ptr + i * size, key, size); 
     _qsort(ptr, lrange, i - 1, size, cmp); 
     _qsort(ptr, i + 1, rrange, size, cmp); 
    } 
} 

я пишу простой тест на целочисленный массив, это КСС Funciton:

int cmp(const void *x, const void *y) 
{ 
    return *(int *)x - *(int *)y; 
} 

Это вызывает дамп, но когда я измените тип lrange, rrange, i, j от size_t до int, он работает правильно, я не могу понять, почему?

Answer 1

size_t i, j; 

являются неподписанными типами. Если значение неподписанной переменной равно 0, а 1 вычитается, значение будет округлено до максимально возможного значения для этого неподписанного типа.

Это может произойти на линиях:

j--; 

и:

_qsort(ptr, lrange, i - 1, size, cmp); 

Когда это недопустимое значение используется в качестве индекса для массива, то это вызовет SEG-вины, так как программа не может читать адрес, который выходит за пределы.

---

Не используйте имена с префиксом _, _qsort, как те, которые зарезервированы для реализации.

Answer 2

memcpy(key, ptr + i * size, size); 

ptr является void *, вы не можете использовать арифметические операции над указателями с void *, переключитесь на char * (как qsort в стандартной библиотеке).