Bucket Sort Algorithm

Bucket Sort is a distribution-based sorting algorithm that distributes elements into buckets, sorts each bucket individually, and then merges them to produce a fully sorted array.

In this article, we will understand the Bucket Sort algorithm from scratch and also learn the pseudocode, flowchart, and detailed working of the bucket sort algorithm. We will also implement the bucket sort algorithm in four major languages used for data structures and algorithms: Python, Java, JavaScript, and C++.

Table of Contents:

• What is Bucket Sort Algorithm?
• Pseudo-code of Bucket Sort Algorithm
• Step by Step Working of Bucket Sort Algorithm
  • Step 1: Define the Number of Buckets
  • Step 2: Scatter the elements in their respective buckets
  • Step 3: Sort individual Buckets
  • Step 4: Gather all the elements
• Implementation of Bucket Sort Algorithm
  • Bucket Sort Algorithm in C++
  • Bucket Sort Algorithm in Java
  • Bucket Sort Algorithm in Python
  • Bucket Sort Algorithm in Javascript
• Time and Space complexity of Bucket Sort
• When to use Bucket Sort?
• Conclusion

What is Bucket Sort Algorithm?

Bucket Sort is a sorting algorithm that follows the scatter-and-gather principle. First, all the elements are scattered and divided into different groups called buckets. Then, they are sorted and gathered to give the final sorted array of elements. You can use any sorting algorithm to sort the elements within each bucket or recursively use the Bucket Sort algorithm.

Note: Bucket Sort works best when the data is uniformly distributed over a known range, meaning that elements are spread evenly and not clustered at specific points. For example, in the example [2, 7, 16, 22, 27, 32, 38, 44], the difference between adjacent elements is almost equal to 5.

Here is the algorithm for Bucket Sort. 

1. Create n empty buckets, where n is based on the input size or range of values.
2. Traverse the input array and insert each element into the appropriate bucket based on its value.
3. Sort each non-empty bucket individually using a suitable sorting algorithm (e.g., insertion sort or quicksort).
4. Concatenate all the sorted buckets and get the final sorted array.

Get Interview-Ready with In-Depth Data Structures Training!

Join Now and level up your problem-solving skills!

Explore Program

Pseudo-code of Bucket Sort Algorithm

The pseudo-code for the Bucket Sort algorithm is as follows:

 BUCKET_SORT(A)
   max_val ← maximum value in a
   k ← number of buckets (e.g., k = n)

    create k empty buckets: bucket[0...k-1]

    for i = 0 to n - 1 do:
        bi ← floor(a[i] * k / (max_val + 1))
        insert a[i] into bucket[bi]

    for j = 0 to k - 1 do:
        if bucket[j] is not empty:
            sort bucket[j]

    sorted_array_index ← 0

    for j = 0 to k - 1 do:
        for each element e in bucket[j] do:
            a[sorted_array_index] ← e
            sorted_array_index ← sorted_array_index + 1
    return a
   

Flowchart of Bucket Sort Algorithm 

Step-by-Step Working of Bucket Sort Algorithm

Let us take the above example of an array [44, 7, 22, 2, 27, 38, 32, 16]. Using this example, we will understand the step-by-step working of Bucket Sort. 

Step 1: Define the Number of Buckets

First, you have to choose the number of buckets, k. This is based on the size and distribution of the input data, that is, the array. We take a look at the max element to decide. In the above example, the maximum element is 44. Therefore, we can divide the range into 5 buckets, each covering a range of 10 units.

If the value of k is already given, calculate the range of each bucket. 

Step 2: Scatter the elements in their respective buckets

When you are not given the value of k, you can scatter the element in two ways. Either you decide the element’s place using the range, or you mathematically calculate it using a formula.

1. Using mathematical formula

We will calculate the bucket each should be assigned to using the formula

2. Using the range

We assign a range for the bucket and assign an element to the bucket if it lies in that range. In this example, the range assigned to each bucket is:

Bucket 0: 0-10
Bucket 1: 10-20
Bucket 2: 20-30
Bucket 3: 30-40
Bucket 4: 40-50

Now assigning elements to their respective buckets, we have: 

When the value of k is given, you will have to calculate the range for each bucket. Once you have that, you can assign each element according to which range it lies in. The range of the bucket can be calculated using the following formula.

In our example, the range of each bucket is 

Range = (44 – 2) / 5 = 8.4 ≈ 8

Bucket 0: 0-8
Bucket 1: 9-16
Bucket 2: 17-24
Bucket 3: 25-32
Bucket 4: 33-40

Step 3: Sort individual Buckets

Now you have to sort each bucket individually. The buckets will look like this after sorting:

Step 4: Gather all the elements

This is the final step. Once you have sorted all the buckets individually, gather them together to get the final sorted array. 

Implementation of the Bucket Sort Algorithm

In this section, we will look at the implementation of the Bucket Sort algorithm in different programming languages like Java, C++, Python, and Javascript. 

Remember, to sort each bucket, you can use any sorting algorithm like quicksort, merge sort or any other algorithm of your choice.

Bucket Sort Algorithm in C++

Code:

Output: 

Explanation: The array is split into buckets using value range and a bucket size of 10. Each bucket is sorted using std::sort(), which typically uses Introsort (a hybrid of QuickSort, HeapSort, and Insertion Sort).

Bucket Sort Algorithm in Java

Code: 

Output:

Explanation: The implementation divides the input into buckets based on their value range using a bucket size of 10. Each bucket is sorted using Java’s Collections.sort(), which uses TimSort

Bucket Sort Algorithm in Python

Code: 

Output:

Explanation: The elements are grouped into buckets based on the range of values and bucket size. Each bucket is sorted using Python’s built-in sorted(), which implements TimSort.

Bucket Sort Algorithm in JavaScript

Code: 

Output:

Explanation: The elements are distributed into buckets by range, using a bucket size of 10. Each bucket is sorted using Array.prototype.sort() with a comparator, which in V8 (used by Chrome/Node.js) is TimSort.

Time and Space complexity of Bucket Sort

In this section, we will look at the time and space complexity of Bucket Sort.

Time complexity 

• Best Case: If the array is uniformly distributed and the items within buckets are nearly sorted, then the bucket sizes will remain balanced and the sorting will be faster. In this situation, applying Insertion Sort gives a best-case time complexity of O(n + k), where n is the number of elements and k is the number of buckets.
• Worst Case: O(n²), occurs when all elements fall into a single bucket and a quadratic-time sort like insertion sort is used.

Space complexity

The space complexity of Bucket Sort is O(n + k), where n is the number of elements and k is the number of buckets.

When to use Bucket Sort?

• Sorting Floating Point Numbers: Useful for numbers with the range [0 to 1]. In these cases, Bucket Sort Algorithm splits them into intervals and sorts the input efficiently.
• Sorting Integers with a Known Range: Works well if you are aware of the range, like when you are sorting students’ scores on exams ranging from 0 to 1000.
• When the data is Uniformly Distributed: When the data is uniformly distributed, Bucket Sort Algorithm works better because it will fill up the buckets uniformly.
• If you know how the data is distributed (uniform, Gaussian, etc.), you can use the Bucket Sort algorithm for improved performance.
• As a technique in Radix Sort: Bucket Sort is sometimes used as a step in Radix Sort, where the numbers are grouped by their digits.
• When you have to maintain the order: A stable sort may be necessary to maintain the relative order of equal elements, such as sorting students by marks and names. Bucket Sort can be a stable algorithm if the individual buckets are sorted using a stable sorting algorithm, such as insertion sort.

Master the Basics of Data Structures – Free of Cost

Start Learning for Free and build a solid foundation in programming!

Explore Program

Conclusion

As we discussed in this article, the Bucket Sort algorithm is a fast and efficient sorting algorithm, generally ideal for uniformly distributed data over a known range. The basic idea is to divide the input into multiple buckets, then sort each bucket individually and combine the results. You could use various internal sorting algorithms to sort each bucket, such as Insertion Sort. In comparison with other sorting algorithms, under correct conditions, Bucket Sort can perform better. Now that you have a solid understanding of how Bucket Sort works, implementations in various languages, time and space complexity, and its applications, it is now possible for you to utilise Bucket Sort confidently. 

Bucket Sort Algorithm – FAQs