// Bucket Sort is a sorting algorithm that distributes elements into several buckets
// and then sorts these buckets individually.
#include <iostream>
#include <vector>
#include <algorithm> // max_element // sort
void bucketSort(int arr[], int size) {
if (size <= 0) return;
// Find the maximum element to determine the range of buckets
int maxVal = *std::max_element(arr, arr + size);
// Create n empty buckets
std::vector<int> buckets[size];
// Put array elements into different buckets
for (int i = 0; i < size; i++) {
int bucketIndex = (size * arr[i]) / (maxVal + 1);
buckets[bucketIndex].push_back(arr[i]);
}
// Sort individual buckets and concatenate the result
int index = 0;
for (int i = 0; i < size; i++) {
std::sort(buckets[i].begin(), buckets[i].end());
for (int j = 0; j < buckets[i].size(); j++) {
arr[index++] = buckets[i][j];
}
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
int main() {
int arr[] = {23, 89, 10, 3, 60, 81, 7};
int size = sizeof(arr) / sizeof(arr[0]);
bucketSort(arr, size);
std::cout << "Sorted array: ";
printArray(arr, size);
}
/*
run:
Sorted array: 3 7 10 23 60 81 89
*/
