Cを使って基数ソートを実装する

Question

私は数日間、以下の質問に固執しました。私は基数ソートを実装するためにCを使用しましたが、コードの1行を除いてすべてうまくいきました。この問題を解決するために私を助けてください。

私の問題は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

あなたは、コードに問題があります。sizeはbucket_size、その後大きくすることができるので

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

を。

そして、おそらくあなたは、に問題があります。--bucket[(arr[i]/significant_num)%10]は負の数に正しく動作しない0

そしてfind_the_largestその後、11未満、大きくなる可能性があるため

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

を。

あなたは動的にこのように、あなたのバッファにメモリを割り当てることができます。

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

そして、最後（free(semi_sort)）上のメモリを解放することを忘れないでください。