How To Do Bucket Sort In JavaScript

Bucket Sort is an efficient sorting algorithm that distributes elements into several groups or “buckets” and then sorts each bucket individually. After sorting, the buckets are concatenated to form the final sorted array. This algorithm is particularly effective when the input is uniformly distributed over a range.

In this post, we’ll explain how Bucket Sort works, provide a JavaScript implementation, and discuss its time and space complexity, pros and cons, and suitable use cases.

What is Bucket Sort?

Bucket Sort divides the input data into a fixed number of buckets. Each bucket holds a subset of the original data, sorted using another sorting algorithm, typically Insertion Sort (though other algorithms like Quick Sort or Merge Sort could be used). After sorting the buckets individually, they are merged to create the final sorted array.

Bucket Sort is a distribution sort, like Counting Sort and Radix Sort, and is most effective when the input data is spread uniformly across a specific range. It can achieve linear time complexity in some cases, making it faster than comparison-based sorting algorithms like Merge Sort or Quick Sort for certain datasets.

Pseudocode for Bucket Sort

Here’s a basic pseudocode outline for Bucket Sort:

procedure bucketSort(arr)
    n = length(arr)
    # Step 1: Create empty buckets
    create n empty buckets

    # Step 2: Distribute array elements into buckets
    for i = 0 to n - 1 do
        index = calculateBucketIndex(arr[i], n)
        place arr[i] in the appropriate bucket

    # Step 3: Sort each bucket
    for each bucket do
        sort the bucket using Insertion Sort

    # Step 4: Concatenate all sorted buckets
    concatenate all buckets into the original array

Time Complexity of Bucket Sort

• Best Case: O(n + k) – In the best case, when the elements are uniformly distributed, Bucket Sort can achieve linear time complexity, where n is the number of elements and k is the number of buckets.
• Average Case: O(n + k) – The average-case complexity remains linear if the data is uniformly distributed and the buckets are evenly filled.
• Worst Case: O(n²) – In the worst case, if all the elements are placed in a single bucket, Bucket Sort degrades to Insertion Sort with quadratic time complexity.

Space Complexity of Bucket Sort

• Space Complexity: O(n + k) – The algorithm requires extra space for the buckets, which can be up to k buckets, each holding an average of n/k elements.

You can see the Time and Space Complexities of sorting algorithms by visiting our page Sorting Algorithms Table For Time and Space Complexities.

JavaScript Implementation of Bucket Sort

Here’s the JavaScript code for implementing Bucket Sort:

// Function to perform Insertion Sort on a bucket
function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

// Main Bucket Sort function
function bucketSort(arr, bucketSize = 5) {
    if (arr.length === 0) {
        return arr;
    }

    // Step 1: Find minimum and maximum values in the array
    let minValue = Math.min(...arr);
    let maxValue = Math.max(...arr);

    // Step 2: Create buckets
    const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
    const buckets = Array.from({ length: bucketCount }, () => []);

    // Step 3: Distribute array elements into buckets
    for (let i = 0; i < arr.length; i++) {
        const bucketIndex = Math.floor((arr[i] - minValue) / bucketSize);
        buckets[bucketIndex].push(arr[i]);
    }

    // Step 4: Sort each bucket and concatenate all sorted buckets
    arr.length = 0; // Reset the array
    for (let i = 0; i < buckets.length; i++) {
        if (buckets[i].length > 0) {
            insertionSort(buckets[i]);
            arr.push(...buckets[i]); // Concatenate sorted buckets
        }
    }

    return arr;
}

// Example usage
const arr = [29, 25, 3, 49, 9, 37, 21, 43];
console.log("Original array:", arr);
console.log("Sorted array:", bucketSort(arr, 5));

Output:

Original array: [
  29, 25,  3, 49,
   9, 37, 21, 43
]
Sorted array: [
   3,  9, 21, 25,
  29, 37, 43, 49
]

Explanation:

• Step 1: We find the minimum and maximum values in the array to determine the range of values.
• Step 2: We create a number of buckets (bucketCount) based on the range of values and the specified bucketSize.
• Step 3: We distribute each element from the array into the appropriate bucket by calculating its bucket index.
• Step 4: Each bucket is sorted individually using Insertion Sort, and the sorted buckets are concatenated to produce the final sorted array.

Step-by-Step Walkthrough of Bucket Sort

Let’s walk through Bucket Sort using the array [29, 25, 3, 49, 9, 37, 21, 43].

Step 1: Find Minimum and Maximum Values

• Minimum Value: 3
• Maximum Value: 49

Step 2: Create Buckets

We set bucketSize = 5, and using the formula:

bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;

We calculate that we need ten buckets.

Step 3: Distribute Elements into Buckets

To calculate the bucket index, we use the following:

bucketIndex = Math.floor((element - minValue) / bucketSize);

• Distribute each element into its respective bucket:
  • Bucket 0: [3]
  • Bucket 1: [9]
  • Bucket 4: [21, 25, 29]
  • Bucket 7: [37]
  • Bucket 8: [43]
  • Bucket 9: [49]

Step 4: Sort Each Bucket and Concatenate

• Sort each bucket using Insertion Sort:
  • Bucket 4 becomes: [21, 25, 29]
• Concatenate all buckets:
  • [3, 9, 21, 25, 29, 37, 43, 49]

Bucket Sort Visualization

We’ve created an interactive Bucket Sort Visualizer below to deepen your understanding of Bucket Sort. This visual tool demonstrates how numbers are distributed into buckets based on their value ranges and sorted within each bucket. The visualizer shows the step-by-step process, allowing you to observe how elements move between the original array, buckets, and the final sorted array. Choose the number of elements you want in your array, then click Generate Random Array then click Start Bucket Sort.

Pros and Cons of Using Bucket Sort

Pros:

1. Linear Time Complexity for Uniform Data: When the input data is uniformly distributed, Bucket Sort can achieve linear time complexity, making it very efficient.
2. Stable Sort: Bucket Sort is stable, meaning it preserves the relative order of equal elements when used with a stable sorting algorithm like Insertion Sort.
3. Parallelizable: Since each bucket can be sorted independently, Bucket Sort can be easily parallelized to improve performance.

Cons:

1. Inefficient for Non-Uniform Data: If the data is not uniformly distributed, Bucket Sort may degrade to quadratic time complexity, as elements could be placed in a single bucket.
2. Requires Extra Space: Bucket Sort requires extra space to store the buckets, which can be disadvantageous for large datasets.
3. Dependent on Bucket Size: Choosing an appropriate bucket size is critical for performance. A poor choice of bucket size can lead to inefficiency.

Optimal Scenarios for Bucket Sort

Bucket Sort shines in specific circumstances:

1. Evenly spread data: This algorithm excels when handling datasets where values are distributed uniformly across a known range. The more even the spread, the more efficient Bucket Sort becomes.
2. Preserving order of equal elements: Bucket Sort fits the bill if your application requires maintaining the original sequence of identical values (known as a stable sort). This is especially true when combined with a stable algorithm like Insertion Sort for sorting individual buckets.
3. Numerical sorting within defined boundaries: Bucket Sort is particularly adept at organizing numbers when you know your dataset’s upper and lower limits. This makes it an excellent choice for sorting decimal numbers, floating-point values, or integers within a specific range.

Conclusion

Bucket Sort excels in sorting uniformly distributed data within a known range. Distributing elements into buckets and sorting them individually achieves linear time complexity in ideal cases. While it requires extra space and loses efficiency with non-uniform data, Bucket Sort remains a powerful tool for large, predictably distributed datasets. Its unique approach makes it a valuable algorithm in specific sorting scenarios, complementing traditional comparison-based methods in computer science.

Congratulations on reading to the end of the tutorial!

Read the following articles to learn how to implement Bucket Sort:

In Python – How to do Bucket Sort in Python.

In C++ – How to Do Bucket Sort in C++.

Have fun and happy researching!