Sorting is one of the most common tasks in programming, whether you are arranging numbers, grades, or any kind of numerical data. Among various sorting algorithms, Bucket Sort stands out as an intuitive and efficient method, especially when dealing with uniformly distributed data. It works by distributing elements into a number of “buckets” and then sorting each bucket individually. Finally, all the buckets are merged to produce a sorted array.
with hands-on learning.
get the skills and confidence to land your next move.
Bucket Sort is particularly useful when you want fast sorting with nearly uniform data, such as decimal numbers between 0 and 1, scores in a game, or measurements. It combines the idea of divide and conquer with simpler sorting techniques like insertion sort, making it a great choice for beginners to understand how data can be grouped, sorted locally, and then merged globally.
In this article, we will explore several C++ programs to implement Bucket Sort using different approaches. Each program will use predefined data so that beginners can focus on understanding the logic rather than input handling.
Program 1: Basic Bucket Sort with Loops
This first program demonstrates the standard Bucket Sort approach. It divides numbers into buckets, sorts each bucket using insertion sort, and then merges them to create a fully sorted array.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void bucketSort(float arr[], int n) {
vector<float> buckets[n];
for (int i = 0; i < n; i++) {
int index = n * arr[i]; // bucket index
buckets[index].push_back(arr[i]);
}
for (int i = 0; i < n; i++)
sort(buckets[i].begin(), buckets[i].end());
int k = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < buckets[i].size(); j++)
arr[k++] = buckets[i][j];
}
int main() {
float arr[] {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
int n = sizeof(arr) / sizeof(arr[0]);
bucketSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}In this example, each element is assigned to a bucket based on its value. Then, each bucket is sorted individually. Finally, all buckets are combined to form the sorted array. This program is beginner-friendly because it clearly shows how data can be divided and merged while demonstrating the power of using simple helper algorithms like sort().
Program 2: Bucket Sort with Custom Insertion Sort
This version replaces the built-in sort() with a custom insertion sort to sort elements within each bucket. It helps beginners understand how sorting works at the bucket level.
#include <iostream>
#include <vector>
using namespace std;
void insertionSort(vector<float> &bucket) {
for (int i = 1; i < bucket.size(); i++) {
float key = bucket[i];
int j = i - 1;
while (j >= 0 && bucket[j] > key) {
bucket[j + 1] = bucket[j];
j--;
}
bucket[j + 1] = key;
}
}
void bucketSortCustom(float arr[], int n) {
vector<float> buckets[n];
for (int i = 0; i < n; i++) {
int index = n * arr[i];
buckets[index].push_back(arr[i]);
}
for (int i = 0; i < n; i++)
insertionSort(buckets[i]);
int k = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < buckets[i].size(); j++)
arr[k++] = buckets[i][j];
}
int main() {
float arr[] {0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51};
int n = sizeof(arr) / sizeof(arr[0]);
bucketSortCustom(arr, n);
cout << "Sorted array with custom insertion sort: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}By using a custom insertion sort, this program shows beginners how the sorting inside buckets actually works. It reinforces the idea that Bucket Sort is a combination of distributing and sorting locally, giving better control over each step of the process.
Program 3: Bucket Sort for Integers
Bucket Sort is often associated with floating-point numbers between 0 and 1, but it can also be adapted for integers. This version shows how to use integer buckets to sort predefined integers efficiently.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void bucketSortIntegers(int arr[], int n) {
int maxVal = *max_element(arr, arr + n);
int bucketCount = maxVal / 10 + 1;
vector<int> buckets[bucketCount];
for (int i = 0; i < n; i++) {
int index = arr[i] / 10;
buckets[index].push_back(arr[i]);
}
for (int i = 0; i < bucketCount; i++)
sort(buckets[i].begin(), buckets[i].end());
int k = 0;
for (int i = 0; i < bucketCount; i++)
for (int j = 0; j < buckets[i].size(); j++)
arr[k++] = buckets[i][j];
}
int main() {
int arr[] {29, 25, 3, 49, 9, 37, 21, 43};
int n = sizeof(arr) / sizeof(arr[0]);
bucketSortIntegers(arr, n);
cout << "Sorted integer array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}This approach divides integers into buckets based on their range. For example, numbers from 0-9 go into the first bucket, 10-19 into the second, and so on. Sorting within each bucket ensures that the final merged array is fully sorted. Beginners can easily grasp how Bucket Sort adapts to different types of data.
Frequently Asked Questions (FAQ)
Here are some common questions beginners ask about Bucket Sort:
Q1: What is Bucket Sort in C++?
Bucket Sort is a sorting algorithm that distributes elements into buckets, sorts each bucket individually, and then merges all buckets to produce a sorted array.
Q2: Is Bucket Sort faster than other sorting algorithms?
It can be very fast for uniformly distributed data. Its average complexity is O(n + k), where n is the number of elements and k is the number of buckets.
Q3: Can Bucket Sort handle integers and floating-point numbers?
Yes, it works with both types. The distribution into buckets can be adjusted depending on the type of data.
Q4: Is Bucket Sort stable?
It can be stable if the sorting inside each bucket is stable, such as using insertion sort.
Q5: How many buckets should I use?
The number of buckets depends on the range and distribution of data. More buckets can improve sorting speed but use more memory.
Conclusion
Bucket Sort is a powerful and beginner-friendly sorting algorithm, especially for numbers that are uniformly distributed. It teaches important programming concepts like dividing data, local sorting, and merging results. In this article, we explored multiple versions of Bucket Sort in C++, including basic floating-point sorting, a custom insertion sort version, and an integer-adapted approach.
Practicing these examples helps beginners understand how data can be grouped and sorted efficiently. Experiment with different datasets, change bucket sizes, and try your own custom sorting for each bucket. With a little practice, Bucket Sort becomes a natural and versatile tool in your programming toolkit.
