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^{2}).

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- **

How to make the output come out as descending order

ReplyDeleteThese changes in the above code should do it-

Delete// sort buckets

for(List bucket : buckets){

Collections.sort(bucket, Collections.reverseOrder());

}

int i = 0;

for (int j = buckets.length - 1; j >=0; j--) {

List bucket = buckets[j];

System.out.println("bucket- " + bucket);

for(int num : bucket){

intArr[i++] = num;

}

}

// int i = 0;

// // Merge buckets to get sorted array

// for(List bucket : buckets){

// for(int num : bucket){

// intArr[i++] = num;

// }

// }