Bucket Sorting

This is a discussion on Bucket Sorting within the C Programming forums, part of the General Programming Boards category; I have to write a program that takes in a set of unsorted numbers, and then by using bucket sorting, ...

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    8

    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;
    }
    Last edited by rmcl; 11-14-2011 at 10:37 PM.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,300
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Nov 2011
    Location
    Saratoga, California, USA
    Posts
    334
    First, it doesn't compile for me due to
    Code:
    for(count[i]>0; count[i]--)
    Any expression(s) may be omitted from the for() but you must have the semicolons.
    Code:
    for( ; count[i]>0 ; count[i]--)
    Now your logic. If I input 5 for the Amount of Numbers, then you'll create 5 buckets, numbered zero through four. And if I input for values: 9 8 7 6 5, you will attempt to increment bucket[9], bucket[8], etc.. You need to use a different MAX_VALUE to control the creation of your buckets.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bucket Sort or Myth
    By sharris in forum C++ Programming
    Replies: 48
    Last Post: 03-27-2011, 03:53 PM
  2. Bucket Sort
    By bearcat19 in forum C++ Programming
    Replies: 0
    Last Post: 03-07-2003, 11:27 AM
  3. Bucket Sort Problems... Please Help!
    By 67stangman in forum C++ Programming
    Replies: 1
    Last Post: 04-17-2002, 10:13 PM
  4. Bucket Sort...
    By 67stangman in forum C++ Programming
    Replies: 1
    Last Post: 04-17-2002, 12:30 PM
  5. Bucket hashing
    By Supra in forum C Programming
    Replies: 7
    Last Post: 04-04-2002, 04:43 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21