Sorting is an essential concept in programming, and understanding different sorting algorithms is key to improving performance and efficiency. Bucket Sort is a unique sorting method that distributes elements into several “buckets” and then sorts each bucket individually. This algorithm is particularly useful when working with numbers that are uniformly distributed, and it can be very efficient for large datasets.
with hands-on learning.
get the skills and confidence to land your next move.
For beginners, learning Bucket Sort provides a clear illustration of how breaking a problem into smaller parts can simplify complex operations. The algorithm works by first dividing the input data into smaller ranges, sorting each of those ranges, and then combining the results. Implementing Bucket Sort in Dart gives beginners hands-on experience with lists, loops, and sorting techniques while also providing a foundation for understanding more advanced algorithms.
Program 1: Basic Bucket Sort
This program demonstrates the standard Bucket Sort approach. It sorts an array of numbers by dividing them into equally sized buckets, sorting each bucket, and then merging them.
void bucketSort(List<double> arr) {
int n = arr.length;
if (n <= 0) return;
List<List<double>> buckets = List.generate(n, (_) => []);
for (int i = 0; i < n; i++) {
int index = (arr[i] * n).floor();
buckets[index].add(arr[i]);
}
for (int i = 0; i < n; i++) {
buckets[i].sort();
}
int idx = 0;
for (int i = 0; i < n; i++) {
for (double num in buckets[i]) {
arr[idx++] = num;
}
}
}
void main() {
List<double> numbers = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68];
print("Original List: $numbers");
bucketSort(numbers);
print("Sorted List: $numbers");
}This program works by distributing numbers into buckets based on their value, sorting each bucket individually, and merging them. Beginners can see how dividing data into smaller parts makes sorting more manageable and efficient.
Program 2: Bucket Sort Using Loops
This version of Bucket Sort emphasizes explicit looping for insertion into buckets and manual sorting, providing a clear, beginner-friendly view of the algorithm’s mechanics.
void bucketSortLoops(List<double> arr) {
int n = arr.length;
List<List<double>> buckets = List.generate(n, (_) => []);
for (double num in arr) {
int index = (num * n).floor();
buckets[index].add(num);
}
for (int i = 0; i < n; i++) {
for (int j = 1; j < buckets[i].length; j++) {
double key = buckets[i][j];
int k = j - 1;
while (k >= 0 && buckets[i][k] > key) {
buckets[i][k + 1] = buckets[i][k];
k--;
}
buckets[i][k + 1] = key;
}
}
int idx = 0;
for (var bucket in buckets) {
for (double num in bucket) {
arr[idx++] = num;
}
}
}
void main() {
List<double> numbers = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51];
print("Original List: $numbers");
bucketSortLoops(numbers);
print("Sorted List: $numbers");
}In this version, the sorting within each bucket is performed manually using insertion sort. Beginners can better understand the step-by-step mechanics of sorting and how loops control the data flow in the algorithm.
Program 3: Recursive Bucket Sort
Bucket Sort can also be implemented recursively, which adds a conceptual twist for understanding algorithm design. This program sorts each bucket by calling the bucket sort function itself for deeper granularity.
void recursiveBucketSort(List<double> arr) {
int n = arr.length;
if (n <= 1) return; // already sorted
// Find min and max values
double minVal = arr.reduce((a, b) => a < b ? a : b);
double maxVal = arr.reduce((a, b) => a > b ? a : b);
// Stop recursion if all numbers are equal
if (minVal == maxVal) return;
// Create n buckets
List<List<double>> buckets = List.generate(n, (_) => []);
// Place numbers into buckets proportionally
for (double num in arr) {
int index = ((num - minVal) / (maxVal - minVal) * (n - 1)).floor();
buckets[index].add(num);
}
// Recursively sort each bucket
for (var bucket in buckets) {
if (bucket.length > 1) {
recursiveBucketSort(bucket);
}
}
// Flatten buckets back into original array
int idx = 0;
for (var bucket in buckets) {
for (double num in bucket) {
arr[idx++] = num;
}
}
}
void main() {
List<double> numbers = [0.25, 0.36, 0.58, 0.41, 0.29, 0.77];
print("Original List: $numbers");
recursiveBucketSort(numbers);
print("Sorted List: $numbers");
}Using recursion in Bucket Sort shows how smaller problems can be solved within the same algorithm. Beginners can learn the power of recursion for breaking down tasks in a logical and elegant way.
Program 4: Bucket Sort with Dynamic Bucket Count
In this program, the number of buckets is determined dynamically based on the input size, making the algorithm more adaptable for different datasets.
void bucketSortDynamic(List<double> arr) {
int n = arr.length;
int bucketCount = (n / 2).ceil();
List<List<double>> buckets = List.generate(bucketCount, (_) => []);
double maxVal = arr.reduce((a, b) => a > b ? a : b);
for (double num in arr) {
int index = ((num / maxVal) * (bucketCount - 1)).floor();
buckets[index].add(num);
}
for (var bucket in buckets) {
bucket.sort();
}
int idx = 0;
for (var bucket in buckets) {
for (double num in bucket) {
arr[idx++] = num;
}
}
}
void main() {
List<double> numbers = [0.9, 0.7, 0.3, 0.5, 0.8, 0.1];
print("Original List: $numbers");
bucketSortDynamic(numbers);
print("Sorted List: $numbers");
}By adjusting the number of buckets dynamically, the algorithm becomes more flexible and efficient. Beginners can understand how customizing parameters can improve performance for different input sizes.
Program 5: Bucket Sort for Integers
Although Bucket Sort is often used for decimals, it can also sort integers by normalizing them into buckets. This version demonstrates integer handling.
void bucketSortIntegers(List<int> arr) {
int n = arr.length;
int maxVal = arr.reduce((a, b) => a > b ? a : b);
List<List<int>> buckets = List.generate(n, (_) => []);
for (int num in arr) {
int index = ((num / (maxVal + 1)) * n).floor();
buckets[index].add(num);
}
for (var bucket in buckets) {
bucket.sort();
}
int idx = 0;
for (var bucket in buckets) {
for (int num in bucket) {
arr[idx++] = num;
}
}
}
void main() {
List<int> numbers = [42, 32, 33, 52, 37, 47, 51];
print("Original List: $numbers");
bucketSortIntegers(numbers);
print("Sorted List: $numbers");
}This program adapts the Bucket Sort logic to integers by mapping them to a normalized range. Beginners can see that the algorithm is versatile and can be used beyond decimal numbers.
Frequently Asked Questions (FAQ)
Bucket Sort is simple yet raises questions for beginners. Here are some common ones:
Q1: What is the time complexity of Bucket Sort?
The 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 works best for uniformly distributed numbers and datasets where maximum and minimum values are known.
Q3: Is Bucket Sort stable?
Yes, if the sorting of individual buckets is stable, the entire algorithm is stable.
Q4: Can Bucket Sort handle integers and decimals?
Yes, by normalizing the values into buckets, it can handle both integers and floating-point numbers.
Q5: How is Bucket Sort different from Counting Sort?
Bucket Sort distributes numbers into ranges (buckets) and then sorts each bucket, while Counting Sort counts occurrences of each value directly.
Conclusion
Bucket Sort is an intuitive and efficient sorting algorithm, especially for uniformly distributed data. In this article, we explored several implementations, including basic bucket sorting, loop-based sorting, recursion, dynamic bucket count, and integer handling.
For beginners, practicing Bucket Sort enhances understanding of arrays, loops, recursion, and data distribution strategies. By experimenting with different input types and methods, you can build a strong foundation in algorithm design and sorting techniques using Dart.
