C를 사용하여 기수 정렬 구현

Question

나는 며칠 동안 아래 질문에 갇혔다. 기수 정렬을 구현하기 위해 C를 사용했습니다. 한 줄의 코드 만 제외하고 모든 것이 잘되었습니다. 이 문제를 해결할 수 있도록 도와 주시겠습니까?

제 문제는 radix_sort 함수의 첫 번째 줄에 있습니다. int semi_sort[12]을 사용하는 동안 프로그램을 올바르게 실행할 수 있습니다. 그러나, 내가 함수에 전달 된 크기 변수를 사용하고 싶습니다. 그러나 int semi_sort[12] 대신 int semi_sort[size]을 사용하면 프로그램이 중단됩니다. 아무도 왜 그런지 말할 수 있습니까? 그건 그렇고, 난 this link,이 저자의 코드에, 그는 int semiSorted[size] 짓을 참조했다. 이번에이 코드 라인이 작동하는 이유는 무엇입니까?

미리 감사드립니다.

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

#define bucket_size 10 

int find_the_largest(int arr[],int size); 
void display(int arr[],int size); 
void radix_sort(int arr[],int size); 

int main() 
{ 
    printf("------------------------------------------------------\n"); 
    printf("  Hey! This is a radix sort algorithm!\n"); 
    printf("------------------------------------------------------\n\n"); 
    int array[] = {10, 2, 303, 4021, 293, 1, 0, 429, 480, 92, 2999, 14}; 
    int size = sizeof(array)/sizeof(int); 
    int largest_num = find_the_largest(array,size); 
    printf("The unsorted array:"); 
    display(array,size); 
    printf("The radix sort algorithm:\n\n"); 
    radix_sort(array,size); 
    display(array,size); 
    return 0; 
} 

int find_the_largest(int arr[],int size){ 
    int i,max_num=0; 
    for(i=0;i<size;i++){ 
     if(arr[i]>max_num) 
      max_num = arr[i]; 
    } 
    return max_num; 
} 

void display(int arr[],int size){ 
    int i; 
    for(i=0;i<size;i++){ 
     printf(" %d",arr[i]); 
    if(i==size-1) 
     printf("\n\n"); 
    } 
} 

void radix_sort(int arr[],int size){ 

    int semi_sort[12]; 
    int max_num = find_the_largest(arr,size); 
    int i,significant_num = 1; 

    while(max_num/significant_num>0){ 
     int bucket[bucket_size] = {0}; 

     for(i=0;i<size;i++){ 
      bucket[(arr[i]/significant_num)%10]++; 
     } 

     for(i=1;i<size;i++){ 
      bucket[i] += bucket[i-1]; 
     } 

     for(i=size-1;i>=0;i--){ 

      semi_sort[--bucket[(arr[i]/significant_num)%10]] = arr[i]; 
     } 


     for(i=0;i<size;i++) 
      arr[i] = semi_sort[i]; 

     significant_num *= 10; 
    } 
} 

Answer 1

당신은 코드에 문제가 :

for(i=1;i<size;i++){ 
    bucket[i] += bucket[i-1]; 
} 

size 때문에이 bucket_size 다음 클 수 있습니다.

for(i=size-1;i>=0;i--){ 
    semi_sort[--bucket[(arr[i]/significant_num)%10]] = arr[i]; 
} 

--bucket[(arr[i]/significant_num)%10] 때문에이 0

그리고 find_the_largest 음수에 대한 올바른 작동하지 않습니다 다음 11보다 큰 이하가 될 수 있습니다

그리고 아마 당신은에 문제가 있습니다.

semi_sort = malloc(size * (sizeof *semi_sort)); 

을 그리고 끝 (free(semi_sort))에 메모리를하는 것을 잊지 마세요 :

동적 같이, 당신의 버퍼 메모리를 할당 할 수 있습니다.