Bucket Sort Algorithm

Bucket sort is a comparison-based sorting algorithm. A bucket sort is helpful when the input array is uniformly distributed. The bucket sort algorithm divides the unsorted array into several groups termed "buckets." When there are more than two values in the same bucket, they are sorted individually using any sorting algorithm, or bucket sort is used recursively. At last, all the individual buckets are combined to form a sorted array.

A distribution-based sorting method called bucket sort divides data into several categories known as buckets. Bucket Sort divides the components into many buckets according to their values rather than comparing each element with the others. After that, each bucket is sorted separately, typically using a different sorting algorithm like Insertion Sort or the built-in sorted() function in Python. The final sorted array is created by combining all of the sorted buckets.

When the input data is evenly distributed over a predetermined range, bucket sorting performs best. Although it may be modified for integers by employing a suitable bucket assignment approach, it is especially effective for sorting floating-point numbers between 0 and 1. Bucket Sort can perform exceptionally well for appropriate datasets since it reduces comparisons and sorts just small groups of elements.

Working Of Bucket Sort

Step 1: Initialize the Input Array

Suppose an input array of size 8 with floating-type values is given.

bash Arr = [0.47,0.29,0.23,0.66,0.35,0.42,0.51,0.59]

Step 2: Initialize the Buckets

Create an answer array of size 10, where each block (position) of the array is used as a bucket to sort the input array.

bash answer = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

Indexes are followed from 0 to 9.

Step 3: Assign Elements to Buckets

Insert each element from the input array into the bucket according to its range. Here, the bucket range will be [0 to 1], [1 to 2], [2 to 3], [3 to... n-1].

Here, n is the number of elements in the array.

Step 3.1: First iteration

In our example, let's take the first element as 0.47. Multiply 0.47 by the size of the array. That is, 0.47*10 = 4.7. Approximately 4.7 is lying in the bucket whose index value is 4.So, finally, 0.47 is inserted into bucket 4.

The answer array is created after the first iteration.

bash answer= [0,0,0,0.47,0,0,0,0]

Step 3.2: Second iteration

Take the second element as 0.29. Multiply 0.29 by the size of the array. That is 0.29*10 = 2.9 (2.9 2). Approximately 2.9 lies in the bucket whose index value is 2.

So, finally, 0.29 is inserted into bucket 2. After the second iteration, the answer array is:

bash answer= [0,0,0.29,0,0.47,0,0,0,0]

Perform this operation until all elements are inserted into the bucket.

Step 3.3: Last iteration

The last iteration answer array looks like this-

bash Answer = [0,0, (0.29,0.23)], 0.35, (0.47,0.42)), (0.51,0.59)], 0.66,0,0,0]

Step 4: Sort the Elements in Each Bucket

The answer element of each bucket with more than two values is sorted using any sorting algorithm, or bucket sort is used recursively.

After this step, the answer array will look like this:

bash Answer = [0,0, (0.23,0.29),0.35, (0.42,0.47), (0.51,0.59), 0.66,0,0]

Step 5: Concatenate All Buckets

After collecting all the elements into each of the buckets, the final array will look like this:

bash Final = [0.23,0.29,0.35,0.42,0.47,0.51,0.59,0.66]

Return the final array. The final array is a sorted array

Bucket Sort Algorithm

1. Create N empty Bucket.
2. Do the following for every array element array[i].
      - insert array[i] into bucket [N*array[i]]
3. sort individual buckets using any of the sorting algorithms.
4. Combine and return all the sorted buckets.

Step 1: Create N Empty Buckets

bash Create N empty buckets.

First, make N empty buckets, where N is the input array's element count.

Elements that fall within a particular range of values are stored in each bucket.

At first, every bucket is empty. By dividing the data into smaller groupings, these buckets improve the efficiency of sorting.

Step 2: Insert Each Element into the Appropriate Bucket

bash For every array element array[i],
insert array[i] into bucket[N × array[i]]

Go through each element in the input array one at a time.

Determine the bucket index for each element using:

N × array[i] is the bucket index. The bucket number is determined by the integer portion of this value.

Place the component in the appropriate bucket. The same bucket is used for elements with comparable values.

Step 3: Sort Individual Buckets

bash Sort individual buckets using any sorting algorithm.

Each bucket is sorted independently once all components have been distributed.
Sorting is not necessary if a bucket only has one element.

Use a sorting technique like this if a bucket has more than one element:
Insertion Sort
Quick Sort
Merge Sort
Python's sorted() function.

Step 4: Combine and Return All the Sorted Buckets

bash Combine and return all the sorted buckets.

From the first to the last bucket, visit each one.
Each bucket's sorted elements should be copied into the original array.
The final array is fully sorted as each bucket has previously been sorted and the buckets are processed sequentially.

Bucket Sort Code In Python

The next stage is to implement Bucket Sort in Python after comprehending its algorithm and operating concept. The program that follows shows how Bucket Sort generates buckets, assigns elements to each bucket, sorts each bucket separately, and then combines all of the buckets to make the sorted array. Floating-point values between 0 and 1 can be sorted using this technique.

Bucket Sort in Python

# Bucket Sort
def bucketsort(arr):
    bucket = []

    # Create empty buckets
    for i in range(len(arr)):
        bucket.append([])

    # Insert elements into their respective buckets
    for i in arr:
        index = int(10 * i)
        bucket[index].append(i)

    # Sort each bucket
    for i in range(len(arr)):
        bucket[i] = sorted(bucket[i])

    # Merge all buckets into the original array
    temp = 0
    for i in range(len(arr)):
        for j in range(len(bucket[i])):
            arr[temp] = bucket[i][j]
            temp += 1

    return arr


# Driver Code
arr = [0.47, 0.29, 0.23, 0.66, 0.35, 0.42, 0.51, 0.59]

print("Sorted array using Bucket Sort:")
print(bucketsort(arr))

Step 1: Define the Function and Create Empty Buckets

def bucketsort(arr):
    bucket = []

    for i in range(len(arr)):
        bucket.append([])

The input array is sorted using the bucketsort() function. The bucket is initialized as an empty list.

To store elements according to their values, a loop creates empty buckets—one bucket for each element in the array.

Step 2: Distribute Elements into Buckets

for i in arr:
    index = int(10 * i)
    bucket[index].append(i)

One by one, the input array's elements are processed.
The formula for the bucket index is int(10 * i).
Based on its value, the element is placed into the appropriate bucket.

Step 3: Sort Each Bucket

for i in range(len(arr)):
    bucket[i] = sorted(bucket[i])

Python's built-in sorted() method is used to sort each bucket separately.
Buckets with one or no elements stay the same.

Step 4: Merge the Sorted Buckets

temp = 0
for i in range(len(arr)):
    for j in range(len(bucket[i])):
        arr[temp] = bucket[i][j]
        temp += 1

Each bucket's sorted elements are replicated into the initial array.
The position in the original array is tracked by the variable temp.
This creates a single, fully sorted array from all of the buckets.

Step 5: Return the Sorted Array

return arr

Once all buckets have been combined, the function returns the final sorted array.

Step 6: Call the Function and Display the Output

arr = [0.47, 0.29, 0.23, 0.66, 0.35, 0.42, 0.51, 0.59]

print("Sorted array using Bucket Sort:")
print(bucketsort(arr))

It creates a floating-point input array.
The array is used as input when the bucketsort() function is called.
The sorted array is then printed.

Output

bash Sorted array using Bucket Sort:
[0.23, 0.29, 0.35, 0.42, 0.47, 0.51, 0.59, 0.66]

Bucket Sort Code In Java

The Bucket Sort algorithm's implementation is shown in the Java program that follows. It makes several buckets, divides the input elements into the appropriate buckets according to their values, sorts each bucket separately, and then combines all of the buckets to produce the sorted array. This approach works well for sorting floating-point values between 0 and 1.

// Bucket sort in Java
import java.util.ArrayList;
import java.util.Collections;
public class BucketSort {
  public void bucketSort(float[] arr, int n) {
    if (n <= 0)
      return;
    @SuppressWarnings("unchecked")
    ArrayList<Float>[] bucket = new ArrayList[n];
    // Create empty buckets
    for (int i = 0; i < n; i++)
      bucket[i] = new ArrayList<Float>();

    // Add elements into the buckets
    for (int i = 0; i < n; i++) {
      int bucketIndex = (int) arr[i] * n;
      bucket[bucketIndex].add(arr[i]);
    }
    // Sort the elements of each bucket
    for (int i = 0; i < n; i++) {
      Collections.sort((bucket[i]));
    }
    // Get the sorted array
    int index = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0, size = bucket[i].size(); j < size; j++) {
        arr[index++] = bucket[i].get(j);
      }
    }
  }
  // Driver code
  public static void main(String[] args) {
    BucketSort b = new BucketSort();
    float[] arr = { (float) 0.42, (float) 0.32, (float) 0.33, (float) 0.52, (float) 0.37, (float) 0.47,(float) 0.51 };
    b.bucketSort(arr, 7);
    for (float i : arr)
      System.out.print(i + "  ");
  }
}

Step 1: Import Required Libraries and Create the Class

import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {

Dynamic buckets are made with the ArrayList class.
Each bucket can be sorted using the sort() function provided by the Collections class.
The Bucket Sort algorithm is implemented in a class called BucketSort.

Step 2: Create Empty Buckets

ArrayList<Float>[] bucket = new ArrayList[n];

for (int i = 0; i < n; i++)
    bucket[i] = new ArrayList<Float>();

An array of ArrayList objects is created to represent the buckets.
A loop initializes each bucket as an empty ArrayList.
These buckets will store the input elements based on their values.

Step 3: Distribute Elements into Buckets

for (int i = 0; i < n; i++) {
    int bucketIndex = (int)(arr[i] * n);
    bucket[bucketIndex].add(arr[i]);
}

One by one, the input array's elements are processed.
Arr[i] * n is used to calculate the bucket index.
Based on its value, the element is placed into the appropriate bucket.

Step 4: Sort Each Bucket

for (int i = 0; i < n; i++) {
    Collections.sort(bucket[i]);
}

Each bucket is sorted individually using Java's built-in Collections.sort() method.
Buckets with zero or one element require little or no sorting.

Step 5: Merge the Sorted Buckets

int index = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < bucket[i].size(); j++) {
        arr[index++] = bucket[i].get(j);
    }
}

The sorted elements from all buckets are copied back into the original array.
The variable index keeps track of the current position in the array.
After merging, the original array becomes completely sorted.

Step 6: Execute and Display the Output

BucketSort b = new BucketSort();

float[] arr = {0.42f, 0.32f, 0.33f, 0.52f, 0.37f, 0.47f, 0.51f};

b.bucketSort(arr, 7);

for (float i : arr)
    System.out.print(i + " ");

A BucketSort class object is generated.
Unsorted values are used to initialize a float array.
The array is sorted by calling the bucketSort() function.
The sorted elements are then displayed on the screen.

Output

0.32  0.33  0.37  0.42  0.47  0.51  0.52  

Bucket Sort Time Complexity

1. Best-Case - O(n+k)

When the elements of the input array are uniformly distributed over the buckets, each bucket has either an equal or nearly equal number of elements.

The time required to make the bucket is denoted by O(n), and O(k) is the amount of time it takes to sort the elements. So the total time complexity of the best case is O (n+k).

2. Average-Case - O(n*n)

When the elements of the input array are distributed randomly over the buckets, then the time complexity is linear. Even if the elements of the input array are not uniformly distributed over the buckets, bucket sort runs in linear time. So the total time complexity of the average case is O (n).

3. Worst-Case - O(n^2)

The worst case occurs when all the elements are placed into the same bucket. This happens when the input values are very close to each other or the bucket distribution is poor. In this situation, Bucket Sort loses its advantage because one bucket contains almost all the elements.

The overall time complexity then depends on the sorting algorithm used to sort that bucket. If Insertion Sort is used and the elements are in reverse order, sorting that bucket takes O(n²) time. Therefore, the worst-case time complexity of Bucket Sort is O(n²).

Application

Floating-Point Number Sorting

Floating-point numbers are frequently sorted using bucket sort, particularly when the values fall within a predetermined range like 0 to 1.

Systems for Database Management

Large datasets can be effectively sorted and organized with it, speeding up data retrieval and searches.

Data Processing and Analytics

For statistical analysis and reporting, bucket sort aids in the grouping and sorting of numerical data.

Computing in Science

It is employed in scientific applications when it is necessary to swiftly sort big collections of consistently dispersed numerical values.

Analysis of Frequency and Histograms

When creating histograms and analyzing data distributions, bucket sorting is helpful for organizing values into intervals, or buckets.

Processing in parallel

Bucket Sort is ideal for distributed and parallel computing systems since each bucket can be sorted individually.

Graphics on Computers

When the data falls inside a predetermined range, it is utilized in graphics programs to effectively sort objects or depth values.

Large Uniformly Distributed Datasets

Bucket Sort is appropriate for many real-world applications because it works well with huge datasets whose values are evenly distributed.

Conclusion

When the input elements are evenly distributed throughout a predetermined range, Bucket Sort, an effective non-comparison sorting technique, works well. To create the final sorted array, it divides the elements into several buckets, sorts each bucket separately, and then merges the sorted buckets.

When the input values are uniformly distributed, Bucket Sort performs exceptionally well for huge datasets, with an average and best-case time complexity of O(n + k). Although it can be modified for other ranges by employing an appropriate bucket assignment technique, it is most useful for sorting floating-point numbers in the range of 0 to 1.

However, the distribution of the items throughout the buckets determines how well Bucket Sort performs. Depending on the sorting method employed within each bucket, the algorithm's performance declines and the worst-case time complexity becomes O(n²) if the majority of elements fall into one bucket.

In applications like data analysis, database systems, scientific computing, and parallel processing, when the input range is known and the data is roughly evenly distributed, bucket sort is a straightforward, quick, and effective sorting method for appropriate datasets.