Bucket Sort - Segmentation error

Question

So I used quicksort in my program but now want to reduce my complexity to O(n). I need to use bucket sort for this to work.

That my program does

My program reads in a file of integers, and the number of integers in the file, and outputs the lowest number in the file which exceeds at least 90% of the numbers in the file.

I did managed to get this to work, using quicksort. However, I am not getting the right output with bucket sort and I have no idea why, because my code seems to be correct.

I get a segmentation fault when running it

My code for Bucket sorting & outputting the result

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

My program outputs compiles and but I get a Segmentation Fault when running it.

Any ideas regarding what I am doing wrong in my BucketSort?

Thank you,

Danielle

Answer 1

These two lines together are a problem, if n is <20 and array contains numbers up to 703K

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

you are writing waaaay out of bounds.

Try this:

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);
}