#include <iostream>
#include <vector>
#include <algorithm>

// Bucket Sort in C++
std::vector<double> bucketSort(std::vector<double>& array) {
    int n = array.size();
    std::vector<std::vector<double>> bucket(n);

    // Insert elements into their respective buckets
    for (int i = 0; i < n; ++i) {
        int index_b = static_cast<int>(n * array[i]);
        if (index_b >= n) {
            index_b = n - 1;
        }
        bucket[index_b].push_back(array[i]);
    }

    // Sort the elements of each bucket
    for (int i = 0; i < n; ++i) {
        std::sort(bucket[i].begin(), bucket[i].end());
    }

    // Get the sorted elements
    int k = 0;
    for (int i = 0; i < n; ++i) {
        for (size_t j = 0; j < bucket[i].size(); ++j) {
            array[k++] = bucket[i][j];
        }
    }
    return array;
}

int main() {
    std::vector<double> array = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};
    std::cout << "Sorted Array is\n";
    std::vector<double> sortedArray = bucketSort(array);
    
    for (double val : sortedArray) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}