Was ist los mit meiner generischen schnellen Sortierung?

Question

ich eine generische quicksort zu schreiben versuche:

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); 
    } 
} 

ich einen einfachen Test auf einem int-Array schreiben, ist dies die cmp funciton:

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

Es einen Core Dump verursachen, aber wenn ich Ändern Sie den Typ von lrange, rrange, i, j von size_t bis int, es läuft richtig, ich kann nicht verstehen, warum?

Answer 1

size_t i, j; 

sind vorzeichenlose Typen. Wenn ein Wert einer vorzeichenlosen Variablen 0 ist und 1 subtrahiert wird, wird der Wert auf den größtmöglichen Wert für diesen vorzeichenlosen Typ umgebrochen.

Diese auf den Leitungen passieren können:

j--; 

und:

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

Wenn der ungültige Wert als Index für ein Array verwendet wird, wird es einen Segmentation Fault, da das Programm verursachen kann nicht lesen eine Adresse, die außerhalb der Grenzen liegt.

---

Sie Namen nicht mit dem Präfix verwenden _, _qsort, wie die für die Implementierung reserviert ist.

Answer 2

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

ptr ist ein void *, können Sie keine Pointer-Arithmetik mit void * verwenden, wechseln Sie zu char * (als qsort in der Standardbibliothek).