Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: How to know size and number of buckets in bucket sort

  1. #1
    Member
    Join Date
    May 2011
    Posts
    61
    My Mood
    Busy
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default How to know size and number of buckets in bucket sort

    Hi, how do I know what to set the range of values and how many buckets to use with bucket sort?

    E.g. from Wikipedia: [29,25,3,49,9,37,21,43]
    They used 5 buckets of size 10

    I know it's supposed to be a distribution sort (not comparison sort), but unsure how they determined the number of buckets and size of each bucket...Any help appreciated.


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: How to know size and number of buckets in bucket sort

    The actual number of buckets or what range each bucket covers is arbitrary, provided that at least all possible values are covered and that no value can belong to more than 1 bucket.

    For best possible performance the number of elements in each bucket should be as close as possible to each other as possible. You could try finding the min/max of the dataset, then decide how many buckets you want and computing the range of each bucket or vise-versa.

  3. #3
    Member
    Join Date
    May 2011
    Posts
    61
    My Mood
    Busy
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: How to know size and number of buckets in bucket sort

    I'm still confused, would appreciate further clarification if not too much trouble. Let's use the OP example. So this is from WIkipedia, and is it only one bucket array, so we don't have multiple arrays of size 10 (what Wikipedia example decided to use for each bucket range (size) ). And what about duplicates, because I keep seeing the use of an array where each servers as a reference to a head node that points to a linked list and we just insert nodes with values in a range to be at front of this linked list so insert in O(1). Any help appreciated.

  4. #4
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: How to know size and number of buckets in bucket sort

    How each bucket is implemented isn't terribly important, they just need to be able to hold stuff and sort them.

    There are multiple buckets, there are 5 buckets each with range(10).

    So all values [0,10) goes into bucket 1, all vales [10, 20) goes int bucket 2, ... and so on. There's no overlap and every possible value is covered.

    After scattering all the values, each bucket can be sorted the gathered back together.

Similar Threads

  1. Jpanel preffered size exceed the nactual screen size
    By manish.ctae@gmail.com in forum AWT / Java Swing
    Replies: 2
    Last Post: October 31st, 2012, 02:29 AM
  2. How to call a C sort function to sort a Java Array.
    By Dwere13 in forum Java Native Interface
    Replies: 22
    Last Post: July 12th, 2012, 05:44 PM
  3. [SOLVED] counting number of comparisons in merge sort
    By mia_tech in forum What's Wrong With My Code?
    Replies: 9
    Last Post: May 27th, 2012, 12:54 AM
  4. Bucket Sort Help
    By itispj in forum What's Wrong With My Code?
    Replies: 2
    Last Post: October 15th, 2011, 10:59 PM
  5. [SOLVED] Bucket or Bin Sort
    By itispj in forum Java Theory & Questions
    Replies: 1
    Last Post: October 15th, 2011, 07:14 PM