Bucket Sort

Bucket Sort

Description: Bucket sort is a distribution sorting algorithm that divides the elements of an array into several "buckets." Each bucket is then sorted individually, either using a different sorting algorithm or recursively applying bucket sort. The sorted buckets are then concatenated to produce the final sorted array.

How It Works

1. Create Buckets: Divide the range of the input data into a number of buckets. The number of buckets can be determined based on the expected distribution of the input.
2. Distribute Elements: Iterate through the input array, placing each element into the appropriate bucket based on its value.
3. Sort Each Bucket: Sort each non-empty bucket. This can be done using a suitable sorting algorithm (like insertion sort or quicksort).
4. Concatenate Buckets: Finally, concatenate the sorted buckets to produce the sorted output.

Time Complexity

• Worst Case: $O(n^2)$ — occurs when all elements are placed into a single bucket.
• Average Case: $O(n + k)$ — where $n$ is the number of elements and $k$ is the number of buckets.
• Best Case: $O(n + k)$

Space Complexity

• Space Complexity: $O(n + k)$ — additional space is required for the buckets.

Stability

• Stability: Bucket sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements.

Example Code

Here's a C++ implementation of bucket sort:

#include <iostream>
#include <vector>
#include <algorithm> // For std::sort
using namespace std;

// Function to perform bucket sort
void bucketSort(vector<float>& arr) {
    int n = arr.size();
    if (n <= 0) return;

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

    // Put array elements into their respective buckets
    for (float num : arr) {
        int bucketIndex = n * num; // Assuming num is in range [0, 1)
        buckets[bucketIndex].push_back(num);
    }

    // Sort each bucket and concatenate results
    for (int i = 0; i < n; i++) {
        sort(buckets[i].begin(), buckets[i].end());
    }

    // Clear the original array
    arr.clear();

    // Concatenate all sorted buckets
    for (const auto& bucket : buckets) {
        for (float num : bucket) {
            arr.push_back(num);
        }
    }
}

int main() {
    vector<float> arr = {0.42, 0.32, 0.23, 0.52, 0.31, 0.55, 0.87, 0.19};
    bucketSort(arr);

    cout << "Sorted array: ";
    for (float num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Explanation of the Code

1. Function Definition: The bucketSort function takes a vector of floats as input.
2. Bucket Creation: The number of buckets is determined by the size of the input array.
3. Distribution of Elements:
   • Each element is placed into a bucket based on its value. The calculation n * num assumes that the input is normalized to the range $[0, 1)$.
4. Sorting Buckets:
   • Each bucket is sorted individually using the standard library's sort function.
5. Concatenation:
   • After sorting, all the elements from the buckets are concatenated back into the original array.
6. Output: The sorted array is printed.

Conclusion

Bucket sort is particularly useful for sorting uniformly distributed data over a range. Its average-case time complexity of $O(n + k)$ makes it efficient for large datasets when the number of buckets is proportional to the number of elements. However, its performance can degrade if the data is not uniformly distributed or if too few buckets are used. Despite this, bucket sort can be a powerful sorting technique when applied in the right contexts, especially in combination with other sorting algorithms for bucket sorting.