Ошибка в алгоритме сортировки в C (изменение порядка Radix)

Question

Я изучаю C, и я прочитал некоторые алгоритмы сортировки в Интернете. Я попытался сделать свой собственный алгоритм сортировки, и он немного похож на сортировку radix. Radix sort on Wikipedia. Ниже приведена программа с моим алгоритмом сортировки.

#include <stdio.h> 
#include <stdlib.h> 

/* prints all elements of an array of n length */ 
void printArray(int *arr, int n){ 
    if (n < 0){ 
    return; 
    } else if (n == 0){ 
    printf("()\n"); 
    } else { 
    int i; 
    printf("(%d", arr[0]); 
    for(i=1; i<n; i++){ 
     printf(", %d", arr[i]); 
    } 
    printf(")\n"); 
    } 
} 

/* safe replacement for malloc. */ 
void *safeMalloc(int size) { 
    void *ptr = malloc(size); 
    if (ptr == NULL) { 
    printf("\nError: memory allocation failed....abort\n"); 
    printf("\nNot enough space for %d int numbers\n", size); 
    exit(-1); 
    } 
    return ptr; 
} 

/* safe replacement for realloc. */ 
int *resizeArray(int *arr, int newSize){ 
    int *ptr = realloc(arr, newSize*sizeof(int)); 
    if (ptr == NULL) { 
    printf("\nError: memory allocation failed....abort\n"); 
    exit(-1); 
    } 
    return ptr; 
} 

/* check if array is sorted */ 
void checkArray(int length, int *a){ 
    int i; 
    for(i=0; i<length-i; i++){ 
    if (a[i] > a[i+1]){ 
     printArray(a, length); 
     printf("Error in: %d\n", i); 
     return; 
    } 
    } 
} 

/*/////////////////////////////////////////////////// 
* /////////////// SORTING ALGORITHM //////////////// 
* ////////////////////////////////////////////////*/ 
void sort(int length, int a[], int digits){ 
    /* base case */ 
    if ((length <= 1) || (digits == 0)){ 
    return; 
    } 
    /* recursive case */ 
    /* declare variables */ 
    int i, j, digit, idx = 0, sum = 0; 
    int *copy[10], lengthCopy[10]; 
    for(i=0; i<10; i++){ 
    lengthCopy[i] = 0; 
    copy[i] = safeMalloc(sizeof(int)); 
    } 
    for(i=0; i<length; i++){ 
    /* get the n'th digit. Example: a[i]=12345 and digits=100 --> digit=3 */ 
    digit = (a[i]/digits)%10; 

    lengthCopy[digit]++; 
    if (lengthCopy[digit] > 1){ 
     resizeArray(copy[digit], lengthCopy[digit]); 
    } 
    copy[digit][lengthCopy[digit]-1] = i; 
    } 
    /* Get the values */ 
    for(i=0; i<10; i++){ 
    for(j=0; j<lengthCopy[i]; j++){ 
     copy[i][j] = a[copy[i][j]]; 
    } 
    } 
    /* fill in the elements of copy in the original array */ 
    for(i=0; i<10; i++){ 
    for(j=0; j<lengthCopy[i]; j++){ 
     a[idx] = copy[i][j]; 
     idx++; 
    } 
    /* copy[i] is no longer necessary, so free it */ 
    free(copy[i]); 
    } 

    for(i=0; i<10; i++){ 
    /* call recursive function */ 
    sort(lengthCopy[i], &a[sum], digits/10); 
    sum += lengthCopy[i]; 
    } 
} 

int getMax(int length, int a[]){ 
    int i, max = 1; 
    for(i=0; i<length; i++){ 
    while(a[i] > max*10){ 
     max *= 10; 
    } 
    } 
    return max; 
} 

int main(int argc, char *argv[]){ 
    int i, *a, length=20; 
    a = safeMalloc(length*sizeof(int)); 
    for(i=0; i<length; i++){ 
    a[i] = rand()%100; 
    } 
    sort(length, a, getMax(length, a)); 
    checkArray(length, a); 
    printArray(a, length); 
    free(a); 
    return 0; 
} 

Теперь очень странная вещь, когда я опробовал свою программу, является то, что ошибка сегментации происходит, когда я был в основном функции: длина INT = 1000, но если я напечатал: ИНТ длина = 20 ;

Я не знаю, откуда эта ошибка. Кто-нибудь может мне помочь?

Спасибо заранее,

Патрик

P.S. Извините за мой английский, это не мой первый languague;)

Answer 1

Как предложил Рубенс, используя Valgrind приводит вас прямо к ошибке:

==7369== Invalid write of size 4 
==7369== at 0x400991: sort (/tmp/t.c:77) 
==7369== by 0x400BF2: main (/tmp/t.c:118) 
==7369== Address 0x4de46e4 is 0 bytes after a block of size 4 free'd 
==7369== at 0x402FD9E: realloc (valgrind/coregrind/m_replacemalloc/vg_replace_malloc.c:661) 
==7369== by 0x4007AA: resizeArray (/tmp/t.c:33) 
==7369== by 0x40096A: sort (/tmp/t.c:75) 
==7369== by 0x400BF2: main (/tmp/t.c:118) 

После того как вы realloc, вы не можете доступ старый массив, вы должен использовать новый массив. Функция resizeArray возвращает новый массив по какой-либо причине; это ошибка, чтобы игнорировать это возвращаемое значение.

Теперь ваша программа все еще «работает», несмотря на эту ошибку, но только случайно. Ошибки коррупции кучи неприятны.