当前位置: 动力学知识库 > 问答 > 编程问答 >

java - Bucket Sort with a max and min value

问题描述:

For an assignment, I have to create a method that implements bucket sort on a array of size 25 that is filled with random integers between 0 and 25 (inclusive) and I have to use the use the max value as a parameter for the method. Max is the largest element in the array(in my code its 25). Then I have to create another method that implements bucket sort on the same array but now its filled with random integers between -25 and 25 (inclusive) but in this method I have to use a max value and a min value which are both passed in. The max value is the same but min is the smallest value in the array(in my code its -25). I completed the first part but I am having trouble figuring out how to change my first method to complete the second part. Here is my first method:

public static void sort( int[] arr, int max )

{

int min = 0;

int [] bucket=new int[max+1];

for (int i=0; i< max; i++) {

bucket[arr[i]]++;;

}

for (int i=0; i<bucket.length; i++) {

for (int j=0; j<bucket[i]; j++) {

arr[min++]=i;

}

}

}

网友答案:

You just have to create buckets to hold values from min to max. For ex if min is -25 and max is 25, then you have to create 51 buckets. If min is -4 and max is 25 then you have to create 30 buckets. So I would change your code to generate the buckets and also a little bit of the inner logic to populate the buckets. Here is how you can do it :

public static void sort( int[] arr, int min, int max )
{
  int nBuckets = max - min + 1;
  int [] bucket=new int[nBuckets];
  for (int i=0; i< arr.length; i++) {
       bucket[arr[i] - min]++;

  }
  int index = 0;
  for (int i=0; i<bucket.length; i++) {
      for (int j =0; j<bucket[i]; j++) {
          arr[index++]=min;
      }
      min++;
  }
}
分享给朋友:
您可能感兴趣的文章:
随机阅读: