Bucket sort code help

Question

Hello. I have three questions about the following code;

  static void funct(int[] list)  {
  final int N = 20;

  java.util.ArrayList[] buckets = new java.util.ArrayList[N];
  for(int i = 0;  i< list.length; i++)  {
     int key = list[i];
     if(buckets[key] = null)
          buckets[key].add(list[i]);
  }
  int k = 0
  for(int i = 0; i <buckets.length; i++)  {
      if(buckets[i] != null)  {
          for(int j = 0; j< buckets[i].size(); j++)
              list[k++] = (Integer)buckets[i].get(j);
      }
  }

}

1. The algorithm has a major shortcoming, is it that it will only work for up to 20 elements and that it has a poor complexity?

2. The point of the code is to sort a list of elements - they are put into an array, then put into buckets, then they are put from the buckets into the array again?

3. Heres the one I'm stumped on, how would you modify the method so that you could pass an array which contains objects of another class instead of integers?

Answer 1

Addressing your questions:

1. That's two shortcomings. Never mind the complexity for a moment; consider how it is supposed to work for more than 20 elements. For a bucket sort, the idea is that you select a bucket based on the position of the element in the total range of elements. The easiest way to do that on a computer with binary-based integers is to select the first few bits (most significant bits) in the number, and use a power-of-two number of buckets, such as 16 or 32. You can get the most significant bits (and therefore figure out the bucket) with an and operation (&). You can then use the bits to select the bucket directly.

2. The idea behind bucket sort is to use an element of radix sort for an initial pass over the input, and then use a different sort (or an iterated radix sort) on the small buckets, which may be small and more easily sorted, or the concatenation of all the buckets (such as back into the array) may be sorted with lesser complexity.

3. Bucket sort is based on knowing the total range of input, so that you can divide up that range into segments and then categorize input individually. The easiest way to do that is if the input is numerical. If the ordering in the input is only relative, and there are no known absolutes and no easy way of figuring out where in the total range any one element is, then bucket sort isn't suitable.

Answer 2

This is a good homework question. Many of the questions are kind of subjective and almost certainly depend on your classwork.

I suggest you make a stab at it yourself because the class lessons will give a better idea of what the instructor is looking for than any answers here.

Besides, if anyone outside a classroom saw this, the answer would be to just use the built-in array sorting and throw this garbage away!