1

そのため、プログラムでクイックソートを使用しましたが、複雑さを O(n) に減らしたいと考えています。これを機能させるには、バケットソートを使用する必要があります。

私のプログラムが行うこと

私のプログラムは、整数のファイルとファイル内の整数の数を読み取り、ファイル内の数値の少なくとも 90% を超える、ファイル内の最小の数値を出力します。

クイックソートを使用して、これを機能させることができました。ただし、バケットソートで正しい出力が得られず、コードが正しいように見えるため、その理由がわかりません。

実行するとセグメンテーション違反が発生します

バケットのソートと結果の出力のための私のコード

void Bucket_Sort(int array[], int n)
{   
 int i, j;   
 int count[n];  
 for(i=0; i < n; i++)
 {   
  count[i] = 0;   
 }     
 for(i=0; i < n; i++)
 {    
  (count[array[i]])++; 
 }     
 for(i=0,j=0; i < n; i++)
 {   
  for(; count[i]>0;(count[i])--) 
  {       
   array[j++] = i; 
  }  
 }   
}    Bucket_Sort(array, numberOfNumbers);   

     //Output the lowest number in the file which exceeds at least 90% of the numbers in the file.
     for (count = floor(0.9 * numberOfNumbers); count < numberOfNumbers; count ++)
     {
      if (array[count] != array[count + 1])
     {
      output = array[count];
      break;    
     }  
     }  
      printf("The outputs is : "); 
      printf("%d \n", output);

プログラムの出力はコンパイルされますが、実行時にセグメンテーション エラーが発生します。

BucketSort で間違っていることに関するアイデアはありますか?

ありがとうございました、

ダニエル

4

1 に答える 1

1

n20 未満で、array最大 703K の数値が含まれている場合、これら 2 行を一緒に使用すると問題が発生します。

int count[n];  
(count[array[i]])++;

あなたは範囲外でwaaaayを書いています。

これを試して：

void Bucket_Sort(int array[], int n)
{
    int i, j;
    int *count = NULL;

    // find largest
    int mymax = array[0]+1;
    for (i=1; i<n; ++i)
    {
        if (mymax < (array[i]+1))
            mymax = array[i]+1;
    }

    // allocate and zero-fill a proper-sized array
    count = calloc(mymax, sizeof(*count));

    for(i=0; i < n; i++)
        (count[array[i]])++;

    for(i=0,j=0; i < mymax; i++)
    {
        for(; count[i]>0;(count[i])--)
            array[j++] = i;
    }
    free(count);
}
于 2013-11-14T21:19:01.243 に答える