Bucket Sort Program in Java

In this post we’ll see how to write Bucket sort program in Java. Bucket sort is one of the O(N) sorting algorithm like Radix sort and Counting sort. Since it runs in linear time (O(N)) so Bucket sort is faster than the comparison based algorithms like Merge Sort or Quick Sort.

Just like Counting sort, Bucket sort also makes some assumption about the input data beforehand like data should be uniformly distributed and should be with in a range.

How does Bucket sort work

Bucket sort works by assigning the input elements to different buckets and then sorting those buckets individually using any sorting technique like insertion sort so the elements in those buckets are sorted. After that merge the buckets to get the sorted output.

For distributing the elements to the buckets uniformly a good hash function is needed. The hash code given by hash function should also be an ordered hash such that if element i is greater than element j then hash(i) should also be greater than hash(j).

Let’s try to clarify working of bucket sort with an example where the elements in input array are with in the range 0..99- {47, 85, 10, 45, 16, 34, 67, 80, 34, 4, 0, 99}

Another array for buckets is needed. Let’s say we want that the elements having hash code 0-9 are put in bucket 0, 10-19 in bucket 1 ..... 90-99 in bucket 9 then we need an array of length 10 for buckets.

Since more than one element may be assigned to the same bucket so a list is needed at each index of the bucket array to store those elements.

With these requirement and the input array as shown above the structure should be as given below.

After sorting individual buckets you will have a structure as shown below.

Now starting from bucket 0 merge all the buckets to get the sorted output.

Bucket sort Java program

Following the steps for bucket sort as explained above you need to create a bucket array and assign a List (preferably linked list) to each array index.

List<Integer>[] buckets = new List[noOfBuckets];
// Associate a list with each index 
// in the bucket array         
for(int i = 0; i < noOfBuckets; i++){
    buckets[i] = new LinkedList<>();
}

Distribute input elements to the buckets as per the calculated hash.
Sort each bucket, for that sort() method of the Collections utility class is used in the program.
Merge buckets, you can use the input array itself as output (sorted array) while merging the buckets.
```
for(List<Integer> bucket : buckets){
  for(int num : bucket){
    intArr[i++] = num;
  }
}
```
Though outer and inner loops are used while merging but in the outer loop you are retrieving the list at each index and then iterating that list in the inner loop so effectively you are linearly traversing all the buckets which should take O(N) time.

Java code

public class BucketSort {
  public static void main(String[] args) {
    int[] intArr = {47, 85, 10, 45, 16, 34, 67, 80, 34, 4, 0, 99};
    //int[] intArr = {21,11,33,70,5,25,65,55};
    System.out.println("Original array- " + Arrays.toString(intArr));
    bucketSort(intArr, 10);
    System.out.println("Sorted array after bucket sort- " + Arrays.toString(intArr));
  }
    
  private static void bucketSort(int[] intArr, int noOfBuckets){
    // Create bucket array
    List<Integer>[] buckets = new List[noOfBuckets];
    // Associate a list with each index 
    // in the bucket array         
    for(int i = 0; i < noOfBuckets; i++){
      buckets[i] = new LinkedList<>();
    }
    // Assign numbers from array to the proper bucket
    // by using hashing function
    for(int num : intArr){
      //System.out.println("hash- " + hash(num));
      buckets[hash(num)].add(num);
    }
    // sort buckets
    for(List<Integer> bucket : buckets){
      Collections.sort(bucket);
    }
    int i = 0;
    // Merge buckets to get sorted array
    for(List<Integer> bucket : buckets){
      for(int num : bucket){
        intArr[i++] = num;
      }
    }
  }
    
  // A very simple hash function
  private static int hash(int num){
    return num/10;
  }
}

Output

Original array- [47, 85, 10, 45, 16, 34, 67, 80, 34, 4, 0, 99]
Sorted array after bucket sort- [0, 4, 10, 16, 34, 34, 45, 47, 67, 80, 85, 99]

Performance of Bucket Sort

Average time complexity of Bucket sort is considered O(n+k) where O(n) is the time spent in distributing elements across the buckets and sorting them and O(k) is the time spent in merging the buckets.

In worst case when most of the elements land in the same bucket time complexity is O(n²).

Space complexity of Bucket sort is O(n+k) as an auxiliary array of size k is needed for buckets. Each index of that bucket array holds reference to a list, total number of nodes in all those lists will be n making the total auxiliary space requirement as (n+k).

That's all for this topic Bucket Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Saturday, April 23, 2022