Welcome to our comprehensive guide on Java Bucket Sort! In this tutorial, we'll dive deep into understanding what Bucket Sort is, why we use it, and how to implement it in Java. By the end of this tutorial, you'll be able to sort large datasets efficiently using Bucket Sort.
Bucket Sort is a sorting algorithm that works by distributing elements of an array to be sorted into a number of sub-arrays, called buckets. Each bucket is then sorted individually, and finally, the sorted buckets are merged back together to form the sorted array.
Bucket Sort is particularly useful when dealing with large datasets that cannot be efficiently sorted by other algorithms like Quick Sort or Merge Sort due to their average-case time complexity of O(n log n). Bucket Sort has an average-case time complexity of O(n + k), where k is the number of elements in the largest bucket. This makes it efficient for sorting large datasets where the elements are relatively evenly distributed across the range of possible values.
The first step in Bucket Sort is to divide the array into a fixed number of buckets, typically based on the range of possible values in the dataset. Each bucket is then initialized to hold the elements that fall within its specific range.
int array[] = {10, 2, 5, 6, 1, 3, 4, 7, 8};
int size = array.length;
int numBuckets = 5; // Assuming max value is less than 25
int maxValue = findMax(array);
int bucketSize = maxValue / numBuckets;
int[][] buckets = new int[numBuckets][];
for (int i = 0; i < numBuckets; i++) {
buckets[i] = new int[bucketSize];
}
for (int i = 0; i < size; i++) {
int index = array[i] / bucketSize;
buckets[index][array[i] % bucketSize]++;
}After initializing the buckets, the next step is to sort each bucket individually. This can be done using any sorting algorithm, such as Insertion Sort, Quick Sort, or Merge Sort.
for (int i = 0; i < numBuckets; i++) {
sort(buckets[i]);
}Finally, the sorted buckets are merged back together to form the sorted array.
int sortedArray[] = new int[size];
int index = 0;
for (int i = 0; i < numBuckets; i++) {
for (int j = 0; j < bucketSize; j++) {
while (buckets[i][j] > 0) {
sortedArray[index++] = i * bucketSize + j;
buckets[i][j]--;
}
}
}In this example, we'll implement a simple Bucket Sort for a small array.
public class BucketSort {
public static void main(String[] args) {
int[] array = {10, 2, 5, 6, 1, 3, 4, 7, 8};
int size = array.length;
int numBuckets = 5;
int maxValue = findMax(array);
int bucketSize = maxValue / numBuckets;
int[][] buckets = new int[numBuckets][];
for (int i = 0; i < numBuckets; i++) {
buckets[i] = new int[bucketSize];
}
for (int i = 0; i < size; i++) {
int index = array[i] / bucketSize;
buckets[index][array[i] % bucketSize]++;
}
for (int i = 0; i < numBuckets; i++) {
sort(buckets[i]);
}
int sortedArray[] = new int[size];
int index = 0;
for (int i = 0; i < numBuckets; i++) {
for (int j = 0; j < bucketSize; j++) {
while (buckets[i][j] > 0) {
sortedArray[index++] = i * bucketSize + j;
buckets[i][j]--;
}
}
}
System.out.println(Arrays.toString(sortedArray));
}
public static void sort(int[] array) {
for (int i = 1; i < array.length; i++) {
int key = array[i];
int j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
}
public static int findMax(int[] array) {
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
return max;
}
}In this example, we'll implement Bucket Sort with variable-sized buckets, which allows for more efficient sorting of datasets with varying ranges of possible values.
What is the average-case time complexity of Bucket Sort?
By the end of this tutorial, you'll have gained a solid understanding of Bucket Sort and how to implement it in Java. Happy coding! 🎉