public static int[] BucketSort(int[] array, int numBuckets){ //TODO: implement b
ID: 3870762 • Letter: P
Question
public static int[] BucketSort(int[] array, int numBuckets){
//TODO: implement bucket sort as described at any of the following links:
//http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/bucketSort.htm
//http://www.geeksforgeeks.org/bucket-sort-2/
//https://en.wikipedia.org/wiki/Bucket_sort
//Your BucketSort should create an array of size numBuckets, with each of these buckets
//able to hold any number of integers. For example, each bucket could be an ArrayList of
//integers. Rather than inserting in the bucket in sorted order, you can fill these buckets
//and then use Collections.sort() on each ArrayList, similar to how Arrays.sort() works.
return null;
}
Explanation / Answer
//The method BucketSort sorts the integer value by placing the elements in the bucket& sorts the element in the bucket.
public static int[] BucketSort(int[] array, int numBuckets){
int largest = array[0];
int smallest = array[0];
//finds the largest and smallest element
for (int i = 1; i < array.length; i++) {
if (array[i] > largest) largest = array[i];
if (array[i] < smallest) smallest = array[i];
}
//declare the list range
double interval = ((double)(largest - smallest + 1))/numBuckets;
//intialize the arraylist
ArrayList<Integer> bucket[] = new ArrayList[numBuckets];
for (int i = 0; i < numBuckets; i++) {
bucket[i] = new ArrayList();
}
//place the element in respective arraylist
for (int i = 0; i < array.length; i++) {
bucket[(int)((array[i] - smallest)/interval)].add(array[i]);
}
int pointer = 0;
for (int i = 0; i < bucket.length; i++) {
Collections.sort(bucket[i]); //sorting all the list
for (int j = 0; j < bucket[i].size(); j++) { //merge the list
array[pointer] = bucket[i].get(j);
pointer++;
}
}
return array;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.