Bucketsort is also called bin sort. Bucket sort first puts the elements of the array or list into different buckets. The first bucket contains elements of the smallest value. The second bucket contains elements that are greater than elements that are present in the first bucket. Similarly, the third bucket contains elements that are greater than the second bucket’s elements, and so on. Thus, buckets are sorted. After that, one by one, each bucket is taken and sorted. Bucket sort is specifically used when input numbers are distributed in a uniform manner over a given range.
In this section, we will implement bucket sort approach in a Java program.
Step I: Create an empty bucket.
Step II: Distribute elements of the input array in such a way that buckets are sorted automatically.
Step III: Iterative over each bucket and check whether it is empty or not. If the bucket is empty, move to the next bucket. If the bucket is not empty, sort the elements present in the array.
Step IV: Concatenate the elements of buckets one by one. The array or list thus formed is the sorted array or list.
Makenbuckets(buckets[n]).// These n buckets can hold a number of different values that fall within the range of the bucket
for(i=0;i<n;i++)// loop through all of the buckets
buckets[i]=0;// assign 0 values to each of the bucket
Java Program The following code implements Bucket sort using the pseudo-code defined above.
// A Java program that does sorting of an array
// using the bucket sort
// import statements
// A method to sort a of length size
// using the bucket sort
// no need to proceed further
//when size is less than or equal to 0
// Step 1
// creating buckets of quantity size
// Step 2
// Placing numbers present in the array a into the different buckets
// typecasting i into integer
// adding elements to the appropriate bucket
// Step 3
// Sorting the individual buckets
// Step 4
// Concatenating all of the buckets into the array a
System.out.println("The array before sorting is: ");
// creating an object of the BucketSort class
// invoking the method bucketSorting ()
// line break
System.out.println("The array after sorting is: ");
The arraybefore sorting is:
The arrayafter sorting is:
Explanation: The size of the input array is 8. Therefore, the first element, 0.697, goes in the 5th bucket [0.697 * 8 = 5.576 => 5 (taking only the integral part)]. The second element goes in the bucket whose index is the integer part of 3.72 (0.465 * 8 = 3.72), which is 3. In the same way, the other elements can also be put into different buckets. The following diagram illustrates the same.
After putting every number in the buckets, the static method sort() is called on each bucket to sort the elements fetched by the buckets.
As per the pseudo-code, the last part is concatenation, which is nothing but re-writing the input array a from starting to ending using the values stored in the buckets. The last for-loop of the method bucketSorting() does the same. The final sorted array is shown below.
Sorting numbers having non-zero integer part
So far, we have only sorted numbers that had integer parts as 0 (see the input of the above example). However, the above program fails when numbers like 1.234 are given. To handle such numbers some modification has to be made in the above program. But first of all, observe the algorithm to sort numbers that have a non-zero integer part.
Step I: Calculate the minimum and maximum elements of the input array.
Step II: Find the range of each bucket.
range = (maximum – minimum) / N
Here, N represents the total number of buckets.
Step III: Make N buckets with the help range calculate above.
Step IV: Spread the elements of the array into these buckets, i.e., bucketIdx = ( array[j] – minimum ) / range
Step V: Now, do the sorting of each of the bucket one by one
Step VI: Collect all the sorted elements from the buckets one by one and do the concatenation to form the sorted array.
Now observe the program that is based on the above algorithm.