Sorting is a fundamental concept in programming, and understanding different sorting algorithms can improve both efficiency and performance in your programs. Bucket Sort is a fascinating algorithm because it sorts elements by distributing them into separate “buckets” based on their value ranges. After distributing, each bucket is sorted individually, and then the results are combined. This approach is particularly efficient for uniformly distributed numbers and provides a clear demonstration of dividing a problem into smaller, manageable tasks.
with hands-on learning.
get the skills and confidence to land your next move.
For beginners, learning Bucket Sort in Java is a great way to strengthen your understanding of arrays, loops, and sorting techniques. It also introduces the concept of bucket-based data organization, which is used in practical applications such as sorting grades, organizing floating-point numbers, and handling large datasets efficiently. By implementing Bucket Sort, you get hands-on experience in breaking down data, processing it in stages, and recombining it to achieve the final sorted output.
Program 1: Basic Bucket Sort
This program demonstrates the standard Bucket Sort approach. It divides numbers into buckets, sorts each bucket, and merges the results to create a fully sorted array.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSortBasic {
public static void bucketSort(double[] arr) {
int n = arr.length;
List<List<Double>> buckets = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
buckets.add(new ArrayList<>());
}
for (double num : arr) {
int index = (int) (num * n);
buckets.get(index).add(num);
}
for (List<Double> bucket : buckets) {
Collections.sort(bucket);
}
int idx = 0;
for (List<Double> bucket : buckets) {
for (double num : bucket) {
arr[idx++] = num;
}
}
}
public static void main(String[] args) {
double[] numbers = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
System.out.println("Original Array:");
for (double num : numbers) System.out.print(num + " ");
System.out.println();
bucketSort(numbers);
System.out.println("Sorted Array:");
for (double num : numbers) System.out.print(num + " ");
}
}This implementation uses the built-in Collections.sort() to sort individual buckets. Beginners can see how dividing data into buckets simplifies sorting and ensures efficiency for uniformly distributed numbers.
Program 2: Bucket Sort Using Loops
This version emphasizes manual sorting within each bucket using loops, which helps beginners understand the algorithm’s step-by-step logic.
import java.util.ArrayList;
import java.util.List;
public class BucketSortLoops {
public static void bucketSort(double[] arr) {
int n = arr.length;
List<List<Double>> buckets = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
buckets.add(new ArrayList<>());
}
for (double num : arr) {
int index = (int) (num * n);
buckets.get(index).add(num);
}
for (List<Double> bucket : buckets) {
for (int i = 1; i < bucket.size(); i++) {
double key = bucket.get(i);
int j = i - 1;
while (j >= 0 && bucket.get(j) > key) {
bucket.set(j + 1, bucket.get(j));
j--;
}
bucket.set(j + 1, key);
}
}
int idx = 0;
for (List<Double> bucket : buckets) {
for (double num : bucket) {
arr[idx++] = num;
}
}
}
public static void main(String[] args) {
double[] numbers = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};
System.out.println("Original Array:");
for (double num : numbers) System.out.print(num + " ");
System.out.println();
bucketSort(numbers);
System.out.println("Sorted Array:");
for (double num : numbers) System.out.print(num + " ");
}
}By manually sorting within each bucket, beginners can clearly follow how insertion sort or simple comparisons work on smaller data sets before merging them.
Program 3: Recursive Bucket Sort
This program implements Bucket Sort recursively, sorting each bucket using the same algorithm if it contains multiple elements.
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
public class BucketSortRecursive {
public static void bucketSort(double[] arr) {
int n = arr.length;
if (n <= 1) return;
double min = arr[0], max = arr[0];
for (double num : arr) {
if (num < min) min = num;
if (num > max) max = num;
}
// Base case: if all values are equal, stop recursion
if (min == max) return;
List<List<Double>> buckets = new ArrayList<>(n);
for (int i = 0; i < n; i++) buckets.add(new ArrayList<>());
double range = max - min + 1e-9; // small offset to prevent division by zero
for (double num : arr) {
int index = (int) ((num - min) / range * n);
if (index >= n) index = n - 1;
buckets.get(index).add(num);
}
int idx = 0;
for (List<Double> bucket : buckets) {
if (bucket.size() > 1) {
double[] subArray = bucket.stream().mapToDouble(d -> d).toArray();
// Recursive call
bucketSort(subArray);
for (double val : subArray) arr[idx++] = val;
} else if (bucket.size() == 1) {
arr[idx++] = bucket.get(0);
}
}
}
public static void main(String[] args) {
double[] numbers = {0.25, 0.36, 0.58, 0.41, 0.29, 0.77};
System.out.println("Original Array:");
for (double num : numbers) System.out.print(num + " ");
System.out.println();
bucketSort(numbers);
System.out.println("Sorted Array:");
for (double num : numbers) System.out.print(num + " ");
}
}Recursion allows the algorithm to handle each bucket individually with the same sorting logic. Beginners can see how breaking down a problem repeatedly leads to a sorted output.
Program 4: Bucket Sort with Dynamic Bucket Count
In this program, the number of buckets is determined dynamically, making the algorithm adaptable for different input sizes.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSortDynamic {
public static void bucketSort(double[] arr) {
int n = arr.length;
int bucketCount = Math.max(1, n / 2);
List<List<Double>> buckets = new ArrayList<>(bucketCount);
for (int i = 0; i < bucketCount; i++) buckets.add(new ArrayList<>());
double maxVal = arr[0];
for (double num : arr) if (num > maxVal) maxVal = num;
for (double num : arr) {
int index = (int) ((num / maxVal) * (bucketCount - 1));
buckets.get(index).add(num);
}
for (List<Double> bucket : buckets) Collections.sort(bucket);
int idx = 0;
for (List<Double> bucket : buckets) {
for (double num : bucket) arr[idx++] = num;
}
}
public static void main(String[] args) {
double[] numbers = {0.9, 0.7, 0.3, 0.5, 0.8, 0.1};
System.out.println("Original Array:");
for (double num : numbers) System.out.print(num + " ");
System.out.println();
bucketSort(numbers);
System.out.println("Sorted Array:");
for (double num : numbers) System.out.print(num + " ");
}
}Using a dynamic bucket count allows the algorithm to adjust to input size and distribution. Beginners can see how parameter tuning can make an algorithm more efficient and adaptable.
Program 5: Bucket Sort for Integers
Although often used for decimal numbers, Bucket Sort can also handle integers by normalizing them into buckets.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSortIntegers {
public static void bucketSort(int[] arr) {
int n = arr.length;
int maxVal = arr[0];
for (int num : arr) if (num > maxVal) maxVal = num;
List<List<Integer>> buckets = new ArrayList<>(n);
for (int i = 0; i < n; i++) buckets.add(new ArrayList<>());
for (int num : arr) {
int index = (int) ((double) num / (maxVal + 1) * n);
buckets.get(index).add(num);
}
for (List<Integer> bucket : buckets) Collections.sort(bucket);
int idx = 0;
for (List<Integer> bucket : buckets) {
for (int num : bucket) arr[idx++] = num;
}
}
public static void main(String[] args) {
int[] numbers = {42, 32, 33, 52, 37, 47, 51};
System.out.println("Original Array:");
for (int num : numbers) System.out.print(num + " ");
System.out.println();
bucketSort(numbers);
System.out.println("Sorted Array:");
for (int num : numbers) System.out.print(num + " ");
}
}This adaptation shows that Bucket Sort is flexible enough to handle both integers and decimals. Beginners can learn how normalization maps numbers into buckets efficiently.
Program 6: Bucket Sort for Integers Including Negative Numbers
This program extends Bucket Sort to handle arrays containing both negative and positive integers. We adjust the bucket indexing based on the minimum value in the array, ensuring that all numbers are correctly placed and sorted.
import java.util.ArrayList;
import java.util.Collections;
public class BucketSortWithNegatives {
public static void insertionSort(ArrayList<Integer> bucket) {
for (int i = 1; i < bucket.size(); i++) {
int key = bucket.get(i);
int j = i - 1;
while (j >= 0 && bucket.get(j) > key) {
bucket.set(j + 1, bucket.get(j));
j--;
}
bucket.set(j + 1, key);
}
}
public static void bucketSort(int[] arr) {
int n = arr.length;
if (n <= 1) return;
int max = arr[0], min = arr[0];
for (int num : arr) {
if (num > max) max = num;
if (num < min) min = num;
}
// Decide reasonable number of buckets
int bucketCount = Math.max(5, n / 2);
double range = (double) (max - min + 1) / bucketCount;
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketCount);
for (int i = 0; i < bucketCount; i++) buckets.add(new ArrayList<>());
// Distribute numbers into buckets
for (int num : arr) {
int bucketIndex = (int) ((num - min) / range);
if (bucketIndex >= bucketCount) bucketIndex = bucketCount - 1;
buckets.get(bucketIndex).add(num);
}
// Sort individual buckets and merge
int index = 0;
for (ArrayList<Integer> bucket : buckets) {
if (!bucket.isEmpty()) {
insertionSort(bucket);
for (int num : bucket) arr[index++] = num;
}
}
}
public static void main(String[] args) {
int[] arr = {42, -5, 32, -10, 37, -1, 51};
System.out.println("Original Array:");
for (int num : arr) System.out.print(num + " ");
System.out.println();
bucketSort(arr);
System.out.println("Sorted Array:");
for (int num : arr) System.out.print(num + " ");
}
}In this program, we first calculate the minimum and maximum values in the array. This allows us to shift all elements by the minimum value when placing them into buckets, which correctly handles negative numbers. Each bucket is sorted using Insertion Sort, and then the buckets are merged back into the original array. This approach shows beginners how Bucket Sort can be adapted to handle a wider range of datasets, including negative values.
Frequently Asked Questions (FAQ)
Bucket Sort is simple but can raise questions for beginners. Here are some common ones:
Q1: What is the time complexity of Bucket Sort?
Average-case complexity is O(n + k), where n is the number of elements and k is the number of buckets.
Q2: When should I use Bucket Sort?
It is ideal for uniformly distributed numbers or floating-point values.
Q3: Is Bucket Sort stable?
Yes, if the sorting within buckets is stable, the overall algorithm is stable.
Q4: Can Bucket Sort handle integers and decimals?
Yes, by normalizing values into buckets, both types can be sorted efficiently.
Q5: How does Bucket Sort differ from Counting Sort?
Bucket Sort divides numbers into ranges and sorts each individually, while Counting Sort counts occurrences of each value directly without dividing into ranges. This makes Bucket Sort more flexible for decimal values or large ranges of numbers, whereas Counting Sort is ideal for small integer ranges.
Conclusion
Bucket Sort is a practical and efficient sorting algorithm, especially for datasets that are uniformly distributed. In this article, we explored multiple implementations in Java, including basic bucket sorting, loop-based sorting, recursive sorting, dynamic bucket counts, and handling integers. Each approach highlights how breaking a problem into smaller parts can simplify sorting and improve efficiency.
For beginners, practicing Bucket Sort strengthens understanding of arrays, loops, recursion, and data organization techniques. Experimenting with different types of inputs and bucket strategies helps build a solid foundation in algorithmic thinking and prepares you for more advanced sorting challenges.
