Bucket sort 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.
Algorithm
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.
Pseudo Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | bucketSorting() Make n buckets (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 } for(int j = 0; j < sizeOfArray; j++) { bIndex -> n * array[j]; Add array[j] to bucket[bIndex]; } for(int j = 0; j < sizeOfArray; j++) { sort bucket[j]; } for(int j = 0; j < n; j++) { for(int i = 0; i < bucket[j].size(); i++) { array[index] -> bucker[j].get(i); index -> index + 1; } } end bucketSorting() |
Java Program
The following code implements Bucket sort using the pseudo-code defined above.
FileName: BucketSortExample.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | // A Java program that does sorting of an array // using the bucket sort // import statements import java.util.*; import java.util.Collections; class BucketSort { // A method to sort a[] of length size // using the bucket sort void bucketSorting(float a[], int size) { if (size <= 0) { // no need to proceed further //when size is less than or equal to 0 return; } // Step 1 // creating buckets of quantity size Vector<Float> bucket[] = new Vector[size]; for (int j = 0; j < size; j++) { bucket[j] = new Vector<Float>(); } // Step 2 // Placing numbers present in the array a[] into the different buckets for (int j = 0; j < size; j++) { float i = a[j] * size; // typecasting i into integer int index = (int) i; // adding elements to the appropriate bucket bucket[index].add(a[j]); } // Step 3 // Sorting the individual buckets for (int j = 0; j < size; j++) { Collections.sort( |