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

- 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.
- Sort buckets separately using any sorting technique like insertion sort or selection sort.
- 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-

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

### 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)**.

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

## No comments:

## Post a Comment