How to write a Bucket Sort program in Java ?

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:

package com.kkjavatutorials.client;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
/**
 * Java Program for Bucket sort
 * @author KK JavaTutorials
 */
public class BucketSortTest {

    public static void main(String[] args) {
    	
    	//Input Array
        int[] inpuArr = {47, 25, 10, 55, 16, 34, 57, 80, 34, 40, 0, 89};
        System.out.println("Original array:" + Arrays.toString(inpuArr));
        
        bucketSort(inpuArr, 10);
        
        System.out.println("Array Sorted After Bucket Sort:" + Arrays.toString(inpuArr));
    }
    
    private static void bucketSort(int[] inputArr, int noOfBuckets){
       
    	/*Create bucket array with specified
    	 number of buclet*/
        List<Integer>[] buckets = new List[noOfBuckets];
        
        /*Now we have to map 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 hash function*/
        for(int num : inputArr){
            buckets[hash(num)].add(num);
        }
        
        
        //Sorting all buckets
        for(List<Integer> bucket : buckets){
            Collections.sort(bucket);
        }
        
        
        int i = 0;
        // FinallymMerge all buckets to get sorted array
        for(List<Integer> bucket : buckets){
            for(int num : bucket){
                inputArr[i++] = num;
            }
        }
    }
    
    /**
     * A very simple implementation of
     * hash function
     * @param number
     * @return
     */
    private static int hash(int number){
        return number/10;
    }
}

package com.kkjavatutorials.client;

import java.util.Arrays;

import java.util.Collections;

import java.util.LinkedList;

import java.util.List;

/**

* Java Program for Bucket sort

* @author KK JavaTutorials

public class BucketSortTest {

public static void main(String[] args) {

//Input Array

int[] inpuArr = {47, 25, 10, 55, 16, 34, 57, 80, 34, 40, 0, 89};

System.out.println("Original array:" + Arrays.toString(inpuArr));

bucketSort(inpuArr, 10);

System.out.println("Array Sorted After Bucket Sort:" + Arrays.toString(inpuArr));

}

private static void bucketSort(int[] inputArr, int noOfBuckets){

/*Create bucket array with specified

number of buclet*/

List<Integer>[] buckets = new List[noOfBuckets];

/*Now we have to map 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 hash function*/

for(int num : inputArr){

buckets[hash(num)].add(num);

}

//Sorting all buckets

for(List<Integer> bucket : buckets){

Collections.sort(bucket);

}

int i = 0;

// FinallymMerge all buckets to get sorted array

for(List<Integer> bucket : buckets){

for(int num : bucket){

inputArr[i++] = num;

}

/**

* A very simple implementation of

* hash function

* @param number

* @return

private static int hash(int number){

return number/10;

}

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 Cancel reply