Bucket Sort in Java

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(bucket[j]);
 }
 // Step 4
 // Concatenating all of the buckets into the array a[]
 // index for re-writing the array a[]
 int idx = 0;
 // iterating over every bucket
 for (int j = 0; j < size; j++)
 {
                // iterating over every element of the bucket
                for (int i = 0; i < bucket[j].size(); i++)
                {
                               // doing the concatenation work
                                a[idx] = bucket[j].get(i);
                                idx = idx + 1;
                }
 }
 }
 }
 public class BucketSortExample
 {
 // Main method
 public static void main(String argvs[])
 {
 // input array
 float a[] = { (float)0.697, (float)0.465, (float)0.756, (float)0.1134,
                (float)0.865, (float)0.885, (float)0.3434, (float)0.5934};
 // calculating size of the input array
 int size = a.length;
 System.out.println("The array before sorting is: ");
 for (int i = 0; i < size; i++)
 {
                System.out.print(a[i] + " ");
 }
 // creating an object of the BucketSort class
 BucketSort bucketSortObj = new BucketSort();
 // invoking the method bucketSorting ()
 bucketSortObj. bucketSorting (a, size);
 // line break
 System.out.println("\n");
 System.out.println("The array after sorting is: ");
 for (int i = 0; i < size; i++)
 {
                System.out.print(a[i] + " ");
 }
 }
 } 
 

Output:

1
2
3
4
5
6
 
 The array before sorting is:
 0.697 0.465 0.756 0.1134 0.865 0.885 0.3434 0.5934
 The array after sorting is:
 0.1134 0.3434 0.465 0.5934 0.697 0.756 0.865 0.885 
 

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.

Algorithm

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.

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
 // A Java program that does sorting of an array
 // using the bucket sort
 // import statements
 import java.util.*;
 import java.util.Collections;
 class BucketSort
 {
 // method for finding the maximum element
 float findMax(float a[], int size)
 {
     float maxEle = a[0];
     for(int i = 1; i < size; i++)
     {
         if(maxEle < a[i])
         {
             maxEle = a[i];
         }
     }
     return maxEle;
 }
 // method for finding the minimum element
 float findMin(float a[], int size)
 {
     float minEle = a[0];
     for(int i = 1; i < size; i++)
     {
         if(minEle > a[i])
         {
             minEle = a[i];
         }
     }
     return minEle;   
 }
 // method for determining the range for every bucket
 int getRange(float minVal, float maxVal, int size)
 {
     int range = ((int)maxVal - (int)minVal) / (int)size;
     return range;
 }
 // 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;
 }
 float maxVal = findMax(a, size);
 float minVal = findMin(a, size);
 int range = getRange(minVal, maxVal, size);
 // determining number of buckets required
 int noofbucket = (int)maxVal - (int)minVal + 1;
 // Step 1
 // creating buckets of quantity noofbucket
 Vector<Float> bucket[] = new Vector[noofbucket];
 for (int j = 0; j < noofbucket; 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++)
 {
                // calculating index of the bucket
                float i = (a[j] - minVal) / range;
                // 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 < noofbucket; j++)
 {
                Collections.sort(bucket[j]);
 }
 // Step 4
 // Concatenating all of the buckets into the array a[]
 // index for re-writing the array a[]
 int idx = 0;
 // iterating over every bucket
 for (int j = 0; j < noofbucket; j++)
 {
                // iterating over every element of the bucket
                for (int i = 0; i < bucket[j].size(); i++)
                {
                               // doing the concatenation work
                                a[idx] = bucket[j].get(i);
                                idx = idx + 1;
                }
 }
 }
 }
 public class BucketSortExample
 {
 // main method
 public static void main(String argvs[])
 {
 // input array
 float a[] = { (float)2.697, (float)1.465, (float)3.756, (float)6.1134,
                (float)0.865, (float)1.085, (float)2.0434, (float)8.0934};
 // calculating size of the input array
 int size = a.length;
 System.out.println("The array before sorting is: ");
 for (int i = 0; i < size; i++)
 {
                System.out.print(a[i] + " ");
 }
 // creating an object of the BucketSort class
 BucketSort bucketSortObj = new BucketSort();
 // invoking the method bucketSorting ()
 bucketSortObj. bucketSorting (a, size);
 // line break
 System.out.println("\n");
 System.out.println("The array after sorting is: ");
 for (int i = 0; i < size; i++)
 {
                System.out.print(a[i] + " ");
 }
 }
 }
 

Output:

1
2
3
4
5
6
 
 The array before sorting is:
 2.697 1.465 3.756 6.1134 0.865 1.085 2.0434 8.0934
 The array after sorting is:
 0.865 1.085 1.465 2.0434 2.697 3.756 6.1134 8.0934 
 

Explanation: The maximum value element is 8.0934, and the minimum value element is 0.865. Therefore, the range of each of the bucket is:

(integer part of (8.0934) – integer part of (0.865)) / 8 => (8 – 0) / 8 = 1.

Thus, the first element of the input array, 2.697 goes to the integer part of ((2.697 – 0.865) / 1) => 1. Thus, the bucket sitting at index 1 stores the number 2.697. Similarly, the index of the buckets can be calculated for other numbers too.

After determining the index of the bucket for every number, the rest of the code behaves in the same way it is behaving in the previous example.

Analysis of the bucket sort

Bucket Sort works on the scattering and gathering approach. Therefore, it is also known as the distribution sort. The bucket sort is sometimes also called the cousin of radix sort, as this sorting algorithm support moving from the most to least significant digits of a number to do the sorting work.

Time Complexity

The time complexity of bucket sort depends on the distribution of the elements. The uniform distribution leads to a better time-complexity when compared with the non-uniform distribution of elements.

The worst time complexity occurs when all the elements are stored in a single container. The time complexity in this scenario is O(n^2), where n is the total number of elements present in the array.

The best time complexity occurs when there is a uniform distribution of elements in the buckets, which means every bucket contains almost an equal number of elements. The time complexity, in this case, is O(n + p), where O(p) is the time complexity of sorting the elements present in the bucket. In this case, we have to use an algorithm that has the linear time complexity to sort the elements present in the bucket. O(n) is the time complexity for the creation of the buckets.

The average time complexity occurs when elements are randomly distributed in the input array. Thus, every bucket does not contain an equal number of elements. The bucket sort algorithm in such a scenario gives the time complexity as O(n + n^2/p + p), where n is the total number of elements and p is the total number of buckets.

Note that conventionally, insertion sort is used to sort the elements present in a bucket.

Space Complexity

Suppose one has created k buckets to do the sorting of a given array. Therefore, till this point, the space complexity is O(k). Now, the maximum number of elements these buckets can hold is the total number of elements present in the input array. If n represents the total number of elements present in the array, then the space complexity of the bucket sort algorithm is O(n + k).

Conclusion

The bucket sort algorithm cannot be used on any given data set. One has to analyze whether the data is uniformly distributed or not. If the data is not uniformly distributed, this is not the algorithm that should be used to accomplish the sorting process.

Note that counting sort gives a glimpse of counting sort. Think of a scenario when each bucket is holding only one element.

Bucket Sort in Java

Related Topics

Pernicious Number in Java

Java exception list

Sliding Window Problem in Java

How to Create Singleton Class in Java

Heart Pattern in Java

Java Integer lowestOneBit()

How to remove last character from String in Java

How to Convert Object to String in Java

Reverse a String using Collections in Java

Contextual keywords in Java

Java Math addExact() Method

Java Control Statements

Java Boolean Class

Difference Between Thread.start() and Thread.run()

Java program to print matrix in Z form

Java Program to Print Permutations of String

Java Generics Questions

Bellman Ford Algorithm in Java

Java calculate age

How to Calculate Week Number From Current Date in Java?