function bucketSort(array, k) is
buckets ← new array of k empty lists
Max ←the maximum key value in the array
Min ←the minimum key value in the array
Divisor = Max-Min/k-1
for i = 0 to length(array)
do insert array[i] into buckets[floor(array[i] - Min/ Divisor)]
for i = 0 to k
do Sort(buckets[i])
return the concatenation of buckets[0] .....buckets[k]
Bucket sort implementation in java.
public class BucketSortExample {
public static void main(String[] args) {
int[] arr = {8, 4, 2, 10, 3, 1, 9, 6, 5, 7};
int numBuckets = 5;
bucketSort(arr, numBuckets);
System.out.println("Sorted array:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void bucketSort(int[] arr, int numBuckets) {
// create empty buckets total numBuckets number of buckets
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(numBuckets);
for (int i = 0; i < numBuckets; i++) {
buckets.add(new ArrayList<Integer>());
}
distributeToBuckets(arr, numBuckets, buckets);
// sort the elements in each bucket
for (ArrayList<Integer> bucket : buckets) {
Collections.sort(bucket);
}
// concatenate the elements in each bucket to obtain the sorted array
int index = 0;
for (ArrayList<Integer> bucket : buckets) {
for (int item : bucket) {
arr[index++] = item;
}
}
}
private static void distributeToBuckets(int[] arr, int numBuckets,
ArrayList<ArrayList<Integer>> buckets) {
// determine minimum and maximum values of input array
int min = Arrays.stream(arr).min().getAsInt();
int max = Arrays.stream(arr).max().getAsInt();
float diff = max - min;
float divisor = diff / (numBuckets - 1);
// place elements into buckets based on value
for (int i = 0; i < arr.length; i++) {
int index = (int) ((arr[i] - min) / divisor);
buckets.get(index).add(arr[i]);
}
}
}
The best case for bucket sort happens when the data can be distributed evenly across the buckets. These leads to a situation when non of the buckets are overloaded. This uniform distribution minimizes the complexity of sorting each bucket, leading to an overall time complexity of O(n+k), where n represents the number of elements and k refers to the number of buckets
Best Case Complexity : O(n+k)
Average Case Complexity : O(n+k)
Worst Case complexity: O(n²)
Space complexity : O(n+k)
Bucket sort is a unique sorting method where the inputs are distributed in individual buckets and then the buckets are sorted using other sorting mechanism.
No comments :
Post a Comment
Please leave your message queries or suggetions.