Example: Bucket Sort Implementation in C++

// Bucket Sort Implementation
#include <iostream>
#include <vector>
#include <algorithm> // For std::sort
#include <iomanip>   // For std::fixed and std::setprecision

// Function to perform Bucket Sort
void bucketSort(std::vector<double>& arr) {
    // Step 1: Determine the number of buckets
    // A common heuristic is to use approximately sqrt(N) or N/K buckets.
    // For simplicity, let's use 10 buckets for numbers between 0.0 and 1.0.
    int numBuckets = 10;
    
    // Step 2: Create 'numBuckets' empty buckets
    std::vector<std::vector<double>> buckets(numBuckets);

    // Step 3: Distribute elements into buckets
    // Iterate through the input array and place each element into its corresponding bucket.
    // The bucket index is calculated by scaling the element value.
    for (double val : arr) {
        // Ensure val is within the expected range [0.0, 1.0) for this scaling
        int bucketIndex = static_cast<int>(numBuckets * val);
        // Handle edge case if val == 1.0, though examples typically use [0.0, 1.0)
        if (bucketIndex >= numBuckets) {
            bucketIndex = numBuckets - 1; // Put 1.0 in the last bucket
        }
        buckets[bucketIndex].push_back(val);
    }

    // Step 4: Sort individual buckets
    // Iterate through each bucket and sort its contents.
    // std::sort uses Introsort (a hybrid of QuickSort, HeapSort, and InsertionSort),
    // which is efficient for smaller collections as well.
    for (int i = 0; i < numBuckets; ++i) {
        std::sort(buckets[i].begin(), buckets[i].end());
    }

    // Step 5: Concatenate sorted buckets
    // Iterate through the buckets and place their sorted elements back into the original array.
    int index = 0;
    for (int i = 0; i < numBuckets; ++i) {
        for (double val : buckets[i]) {
            arr[index++] = val;
        }
    }
}

int main() {
    // Step 1: Initialize an unsorted vector of double values
    std::vector<double> data = {0.72, 0.54, 0.91, 0.12, 0.38, 0.65, 0.29, 0.83, 0.05, 0.47, 0.99, 0.01};

    // Step 2: Print the original array
    std::cout << "Original array: ";
    for (double val : data) {
        std::cout << std::fixed << std::setprecision(2) << val << " ";
    }
    std::cout << std::endl;

    // Step 3: Apply Bucket Sort
    bucketSort(data);

    // Step 4: Print the sorted array
    std::cout << "Sorted array:   ";
    for (double val : data) {
        std::cout << std::fixed << std::setprecision(2) << val << " ";
    }
    std::cout << std::endl;

    return 0;
}