C++ Online Compiler
Example: Bucket Sort Implementation in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// 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; }
Output
Clear
ADVERTISEMENTS