Lecture 356:- Bin Bucket Sort

I believe you meant "Bucket Sort" instead of "Bin Bucket Sort." Bucket Sort is a non-comparative sorting algorithm that distributes elements into a fixed number of buckets and then sorts each bucket individually. It is particularly useful when the input elements are uniformly distributed over a range.

Here's how the Bucket Sort algorithm works:

1. Create an array of empty buckets.
2. Traverse the input array and distribute each element into the appropriate bucket based on some function.
3. Sort each individual bucket (can be done using any sorting algorithm, typically Insertion Sort or another sorting algorithm depending on the range of elements in the bucket).
4. Concatenate all the sorted buckets to obtain the final sorted array.

Here's the C++ implementation of Bucket Sort:

cppCopy code

#include <iostream> #include <vector> #include <algorithm> using namespace std; // Insertion Sort for sorting individual buckets void insertionSort(vector<int>& bucket) {    int n = bucket.size();    for (int i = 1; i < n; i++) {        int key = bucket[i];        int j = i - 1;        while (j >= 0 && bucket[j] > key) {            bucket[j + 1] = bucket[j];            j--;        }        bucket[j + 1] = key;    } } // Bucket Sort function void bucketSort(vector<int>& arr) {    int n = arr.size();    int maxElement = *max_element(arr.begin(), arr.end());    int minElement = *min_element(arr.begin(), arr.end());    // Determine the range and number of buckets    int bucketRange = (maxElement - minElement) / n + 1;    int numBuckets = (maxElement - minElement) / bucketRange + 1;    // Create buckets    vector<vector<int>> buckets(numBuckets);    // Distribute elements into buckets    for (int i = 0; i < n; i++) {        int bucketIndex = (arr[i] - minElement) / bucketRange;        buckets[bucketIndex].push_back(arr[i]);    }    // Sort each bucket individually    for (int i = 0; i < numBuckets; i++) {        insertionSort(buckets[i]);    }    // Concatenate the sorted buckets to get the final sorted array    int index = 0;    for (int i = 0; i < numBuckets; i++) {        for (int j = 0; j < buckets[i].size(); j++) {            arr[index++] = buckets[i][j];        }    } } // Function to display the elements of the array void display(const vector<int>& arr) {    for (int val : arr)        cout << val << " ";    cout << endl; } int main() {    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};    cout << "Original Array: ";    display(arr);    bucketSort(arr);    cout << "Sorted Array: ";    display(arr);    return 0; }

In this implementation, the bucketSort function performs the Bucket Sort algorithm to sort the input array. It uses the insertionSort function to sort each individual bucket. When you run this code, it will display the original array and then the sorted array after applying the Bucket Sort algorithm.