How to write a Bucket Sort program in Java ?

By | July 22, 2020

In this post, we will learn How to write a Bucket sort program in Java.

Bucket sort has a time complexity of O(n) like Radix sort and Counting sort. It runs in linear time O(n) so Bucket sort is faster than the comparison-based algorithms like Quick Sort or Merge Sort.

Similar to the Counting sort, Bucket sort also makes some assumptions about the input data in advance like data should be uniformly distributed and should be within a known range.

How does Bucket Sort work

In bucket sort usually, we assign the input elements to different buckets and then sorting those buckets individually using any sorting algorithm like selection or insertion sort so the elements in those buckets are sorted. After that, we merge the buckets to get the final sorted output.

To distribute the elements to the buckets uniformly we need to have a good hash function. The hash code return by hash function should also be an ordered hash so that if element e1 is greater than element e2 then hash(e1) should also be greater than hash(e2).

Let’s try to understand the working of bucket sort with an example where the elements in the input array are within the range 0..49

Another array of 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 ….. 40-49 in bucket 4 then we need an array of length 5 for buckets.

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

Complete Source Code:

The output of this Program:

Original array:[47, 25, 10, 55, 16, 34, 57, 80, 34, 40, 0, 89]
Array Sorted After Bucket Sort:[0, 10, 16, 25, 34, 34, 40, 47, 55, 57, 80, 89]

Performance of Bucket Sort:

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

In the worst case, if when most of the elements allocate in the same bucket then time complexity is O(n2)

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

You May Also Like:

What is Sorting and why is Sorting Necessary?
Classification of Sorting Algorithms
Java program for Bubble Sort using Iterative Approach
Java program for Bubble Sort using recursive Approach
How to Write a Java program for Selection Sort in Java
How to Write a Java program for Insertion Sort in java?
How to write a Merge sort program in Java
How to write a Quick Sort program in Java
How to write a Radix sort program in Java
Tree Sort Using Binary Search Tree in Java

That’s all about How to write a Bucket Sort program in Java?
If you have any feedback or suggestion please feel free to drop in below comment box.

Leave a Reply

Your email address will not be published.