Thread: Bucket Sorting

I have to write a program that takes in a set of unsorted numbers, and then by using bucket sorting, put all the numbers in that array into numerical order. I thought I had it done perfectly, but when I ran the program using certain array sizes and input values, I ran into some errors. I found that if I input a value for the numbers in the array that is equal to or bigger than the size of the array, the program doesn't function correctly. For example, if the user inputted a array size 12 of: 14 2 3 1 5 6 2 4 3 1 4 2. The output will be: 1 1 2 2 2 3 3 4 4 5 6 2. Not sure why this is happening.

My code:

Code:

#include <stdio.h>void bucket(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;
                }
        }


}




int main()
{
  int array[100]; int n; int i;
    printf("Enter Amount of  Numbers : ");
    scanf("%d",&n);
    printf("Enter the numbers to be sorted:\n");
  for(i = 0; i < n; i++ )
        {  
   scanf("%d",&array[i]);
        }
  printf("\nThe numbers before sorting : \n");
  for (i = 0;i < n;i++)
        {
    printf("%d ", array[i]);
        }
    printf("\nThe numbers after sorting : \n");
  bucket(array, n);
  
  for (i = 0;i < n;i++)
  bucket(array, n);


  for (i = 0;i < n;i++)
        {
    printf("%d ", array[i]);
        }
  printf("\n");
  
           
  return 0;
}

That is not Bucket sort, that is Counting sort.

The problem is edivent on this line:

Code:

count[array[i]]++;

Whatever value array[i] has, that position is looked up in the array. If you type in one-thousand then it's accessing the one-thousandth position in the array.
Have another think about how many items you need in your count array. It is not n, the number of items input, it is something else.

Lastly, check what happens if you type 2 billion as one of the numbers, and consider how you might fix that problem, if at all.