Bucket Sort Java Program

This tutorial shows how to write Bucket sort program in Java. Bucket sort is also one of the linear sort algorithm which runs in O(n) time like Radix sort and Counting sort making Bucket sort faster than Quick sort or Merge sort  both of which run in O(n*logn) time.

Bucket sort makes some assumption about the data that it should be uniformly distributed over a range.

Bucket Sort Algorithm

Bucket sort works by distributing the element over different buckets. Bucket term used here is also an array and the distribution of elements to these buckets is done by using a hash function. The hash function used for calculating hash value must follow these requirements-

  • It returns array indices in range 0..bucket_array_length-1
  • It is ordered: if A[i] < A[j] then hash(A[i]) < hash(A[j])

The steps in Bucket sort are as follows-

  1. Distribute elements to the bucket array using hash function. Associate a list with each bucket array index, if two elements have a same hash i.e. there is a hash collision then append those elements to the list associated with that index.
  2. Sort buckets separately using any sorting technique like insertion sort or selection sort.
  3. Merge the buckets from top to bottom to get a sorted array.

For example if there is an input array with elements in range 0-99 as – [37, 74, 12, 45, 29, 99, 67, 85, 32, 4, 15, 9] and the hash function used is- input_array[i]/10 then bucket array with distribution of elements as per calculated hash is as shown below-

Bucket sort

After sorting the buckets, elements in the buckets would be arranged as given below-
Bucket sort Java

Bucket Sort Java program

public class BucketSort {
  public static void main(String[] args) {
    int[] arr = {37, 74, 12, 45, 67, 99, 65, 29, 32, 9, 15, 4};
    System.out.println("Original array- " + Arrays.toString(arr));
    bucketSort(arr, 10);
    System.out.println("Sorted array after bucket sort- " + Arrays.toString(arr));
  }
	
  private static void bucketSort(int[] arr, int bucketSize){
    // Create bucket array for storing lists
    List<Integer>[] buckets = new List[bucketSize];
    // Linked list with each bucket array index
    // as there may be hash collision 
    for(int i = 0; i < bucketSize; i++){
      buckets[i] = new LinkedList<>();
    }
    // calculate hash and assign elements to proper bucket
    for(int num : arr){
      buckets[hash(num, bucketSize)].add(num);
    }
    // sort buckets
    for(List<Integer> bucket : buckets){
      Collections.sort(bucket);
    }

    int index = 0;
    // Merge buckets to get sorted array
    for(List<Integer> bucket : buckets){
      for(int num : bucket){
        arr[index++] = num;
      }
    }
  }
    
  // hash function used for element distribution 
  private static int hash(int num, int bucketSize){
    return num/bucketSize;
  }
}

Output

Original array- [37, 74, 12, 45, 67, 99, 65, 29, 32, 9, 15, 4]
Sorted array after bucket sort- [4, 9, 12, 15, 29, 32, 37, 45, 65, 67, 74, 99]

Bucket sort time and space complexity

Average time complexity of Bucket sort is O(n + k) where O(k) is the time for creating bucket array and O(n) is the time needed for putting input array elements to the bucket. There are other loops too iterating arrays taking O(n) time but note that O(3n + k) is also considered as O(n + k) as constants are not counted in Big O notation.

In Bucket sort k extra space for bucket array is required. Also there are lists associated with each bucket index where total n elements are stored making total length for lists equal to n. Thus the space complexity of bucket sort is O(n + k).
Related Posts

That’s all for the topic Bucket Sort Java Program. If something is missing or you have something to share about the topic please write a comment.


You may also like

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.