Tutorial 32

 ---- 32 Bucket sort

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// Function to perform insertion sort within each bucket

void insertionSort(vector<float>& bucket)

 {

    int n = bucket.size();

    for (int i = 1; i < n; ++i) {

        float key = bucket[i];

        int j = i - 1;

        while (j >= 0 && bucket[j] > key) {

            bucket[j + 1] = bucket[j];

            --j;

        }

        bucket[j + 1] = key;

    }

}

// Function to perform bucket sort

void bucketSort(vector<float>& arr) 

{

    int n = arr.size();

    vector<vector<float>> buckets(n); // Create n empty buckets

    // Put array elements in different buckets

    for (int i = 0; i < n; ++i) {

        int bucketIndex = n * arr[i];

        buckets[bucketIndex].push_back(arr[i]);

    }

    // Sort individual buckets

    for (int i = 0; i < n; ++i) {

        insertionSort(buckets[i]);

    }

    // Concatenate all buckets into arr

    int index = 0;

    for (int i = 0; i < n; ++i) {

        for (int j = 0; j < buckets[i].size(); ++j) {

            arr[index++] = buckets[i][j];

        }

    }

}

// Function to print the array

void printArray(const vector<float>& arr) {

    for (float i : arr) {

        cout << i << " ";

    }

    cout << endl;

}

// Main function

int main() {

    vector<float> arr = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};

    cout << "Original array: ";

    printArray(arr);

    bucketSort(arr);

    cout << "Sorted array: ";

    printArray(arr);

    return 0;

}