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