bucket_sort_rec.cpp

#include <bits/stdc++.h>
using namespace std;

void insertBucket(vector<vector<float>> &buckets, float value, int n) {
    int index = n * value;
    buckets[index].push_back(value);
    sort(buckets[index].begin(), buckets[index].end());
}

void bucketSort(vector<float> &arr, vector<vector<float>> &buckets, int n,
                int pos) {
    if (n == pos) {
        int index = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < buckets[i].size(); j++)
                arr[index++] = buckets[i][j];
        return;
    }

    insertBucket(buckets, arr[pos],
                 n);  // replace it with the insertion sort implementation
    bucketSort(arr, buckets, n, pos + 1);
}

int main() {
    vector<float> arr = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
    int n = arr.size();
    vector<vector<float>> buckets(n);
    bucketSort(arr, buckets, n, 0);

    cout << "Sorted array is \n";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}