C에서 정렬 알고리즘의 오류 (기수 정렬의 변형)

Question

나는 C를 배우기 때문에 인터넷에서 일부 정렬 알고리즘을 읽습니다. 내 정렬 알고리즘을 만들려고했는데 기수 정렬과 비슷합니다. 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하지만, 내가 입력 한 있지 않은 경우 : INT 길이 = 20 ;

이 오류의 출처를 알 수 없습니다. 누군가 나를 도울 수 있습니까? 사전에

감사합니다,

패트릭

추신 내 영어 죄송합니다, 내 첫 languague 아니다;

Answer 1

은 루벤스가 바로 버그 Valgrind의 당신을 리드하여, 제안 된 것과 같은) : 당신이 수 없습니다 액세스 기존의 배열을, 당신 realloc 후

==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) 

을, 당신 새 배열을 사용해야합니다. resizeArray 함수가 이유 때문에 새로운 배열을 반환합니다. 그 반환 값을 무시하는 버그입니다.

이제 프로그램은 버그에도 불구하고 우연히 "작동"합니다. 힙 손상 버그는 그렇게 불쾌합니다.