Scroll Progress Bar

Bucket sort

Bucket sort is a non-comparison-based sorting algorithm that divides the input into a fixed number of buckets, then sorts each bucket individually, and finally concatenates the sorted buckets to obtain the sorted output. It's efficient when the input data is uniformly distributed. Here's a C++ implementation of bucket sort with comments and Sample Output:

Program:

    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    // Function to perform insertion sort within each bucket
    void insertionSort(std::vector& 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;
        }
    }
    
    // Function to perform bucket sort
    void bucketSort(std::vector& arr, int numBuckets) {
        int n = arr.size();
        
        // Create empty buckets
        std::vector> buckets(numBuckets);
    
        // Distribute elements into buckets
        int maxElement = *std::max_element(arr.begin(), arr.end());
        for (int i = 0; i < n; i++) {
            int index = (arr[i] * numBuckets) / (maxElement + 1);
            buckets[index].push_back(arr[i]);
        }
    
        // Sort each bucket using insertion sort
        for (int i = 0; i < numBuckets; i++) {
            insertionSort(buckets[i]);
        }
    
        // Concatenate the sorted buckets to obtain 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];
            }
        }
    }
    
    int main() {
        std::vector arr = {64, 34, 25, 12, 22, 11, 90};
        int numBuckets = 5;
    
        std::cout << "Original array: ";
        for (int num : arr) {
            std::cout << num << " ";
        }
    
        // Perform bucket sort
        bucketSort(arr, numBuckets);
    
        std::cout << "\nSorted array: ";
        for (int num : arr) {
            std::cout << num << " ";
        }
    
        return 0;
    }
In this code:

insertionSort is a function that performs insertion sort within each bucket.

bucketSort is the main sorting function that creates empty buckets, distributes elements into buckets, sorts each bucket using insertion sort, and concatenates the sorted buckets to obtain the final sorted array.

Sample Output:

    Original array: 64 34 25 12 22 11 90 
    Sorted array: 11 12 22 25 34 64 90

As shown in the sample output, the input vector is successfully sorted using bucket sort. The number of buckets (numBuckets) it can be adjusted to suit the specific input data and distribution.


question

answer

question2

answer2