# What is Bucket Sort

**is a sorting algorithm that works by dividing an array of values into a number of "buckets," or groups. Each bucket represents a range of values that can be sorted independently of the others.**

Bucket sort

Bucket sort

To sort the array, each element is placed into its corresponding bucket based on its value. Once all the elements are in their respective buckets, each bucket is sorted individually (usually using another sorting algorithm, like insertion sort). Finally, the elements are concatenated back together in order to produce the sorted array.

The basic idea behind bucket sort is that by dividing the data into smaller, more manageable pieces, it becomes easier and faster to sort. Additionally, bucket sort can be especially efficient for data sets with a relatively small range of values, as each bucket only needs to hold a small number of values.

## Who invented it?

The

**bucket sort**algorithm is not attributed to a specific inventor, as it is a well-known and widely used algorithm in computer science and has been around for several decades. The concept of bucket sort has been around since the early 20th century, but the modern implementation and analysis of the algorithm were developed in the 1950s and 1960s by several computer scientists, including Kenneth E. Iverson and Harold H. Seward. Since then, the algorithm has been refined and adapted for different applications, and it continues to be an important tool in the field of computer science and data analysis

## Pseudocode

```
bucket_sort(arr, num_buckets):
# Determine the range of values in the array
min_val = minimum value in arr
max_val = maximum value in arr
range_val = max_val - min_val
# Create empty buckets for each range of values
buckets = a list of num_buckets empty lists
bucket_range = range_val / num_buckets
# Place each element into its appropriate bucket
for value in arr:
bucket_index = (value - min_val) / bucket_range
add value to the bucket at index bucket_index
# Sort each bucket
for i in 0 to num_buckets - 1:
sort the list at index i in buckets
# Concatenate the sorted buckets back into the original array
sorted_arr = []
for i in 0 to num_buckets - 1:
append each element of the list at index i in buckets to sorted_arr
return sorted_arr
```

This pseudocode closely follows the steps of the algorithm described above:

- Determine the range of values in the input array
- Create empty buckets for each range of values
- Place each element from the input array into its appropriate bucket
- Sort each individual bucket
- Concatenate the sorted buckets back into the original array to produce the sorted output

## Sample Code

```
// C++ code snippet
// Define a function to perform bucket sort on a vector of values
void bucketSort(vector
```& arr, int num_buckets) {
// Determine the range of values in the array
double min_val = *min_element(arr.begin(), arr.end());
double max_val = *max_element(arr.begin(), arr.end());
double range = max_val - min_val;
// Create empty buckets for each range of values
vector> buckets(num_buckets, vector());
double bucket_range = range / num_buckets;
// Place each element into its appropriate bucket
for (int i = 0; i < arr.size(); i++) {
double value = arr[i];
int bucket_index = int((value - min_val) / bucket_range);
buckets[bucket_index].push_back(value);
}
// Sort each bucket using std::sort
for (int i = 0; i < num_buckets; i++) {
sort(buckets[i].begin(), buckets[i].end());
}
// Concatenate the sorted buckets back into the original array
int index = 0;
for (int i = 0; i < num_buckets; i++) {
for (int j = 0; j < buckets[i].size(); j++) {
arr[index++] = buckets[i][j];
}
}
}
// Main function to test the bucket sort implementation
int main() {
vector arr = {0.42, 0.32, 0.67, 0.25, 0.76, 0.88, 0.11, 0.43, 0.22};
int num_buckets = 3;
bucketSort(arr, num_buckets);
// Print the sorted array
for (int i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}

```
# Python code snippet
def bucket_sort(arr, num_buckets):
# Determine the range of values in the array
min_val = min(arr)
max_val = max(arr)
range_val = max_val - min_val
# Create empty buckets for each range of values
buckets = [[] for _ in range(num_buckets)]
bucket_range = range_val / num_buckets
# Place each element into its appropriate bucket
for value in arr:
bucket_index = int((value - min_val) / bucket_range)
buckets[bucket_index].append(value)
# Sort each bucket
for i in range(num_buckets):
buckets[i].sort()
# Concatenate the sorted buckets back into the original array
sorted_arr = []
for i in range(num_buckets):
sorted_arr += buckets[i]
return sorted_arr
# Example usage
arr = [0.42, 0.32, 0.67, 0.25, 0.76, 0.88, 0.11, 0.43, 0.22]
num_buckets = 3
sorted_arr = bucket_sort(arr, num_buckets)
print(sorted_arr)
```

```
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
public static List
``` bucketSort(List arr, int numBuckets) {
// Determine the range of values in the array
double minVal = Collections.min(arr);
double maxVal = Collections.max(arr);
double rangeVal = maxVal - minVal;
// Create empty buckets for each range of values
List> buckets = new ArrayList<>();
for (int i = 0; i < numBuckets; i++) {
buckets.add(new ArrayList<>());
}
double bucketRange = rangeVal / numBuckets;
// Place each element into its appropriate bucket
for (double value : arr) {
int bucketIndex = (int) ((value - minVal) / bucketRange);
buckets.get(bucketIndex).add(value);
}
// Sort each bucket
for (int i = 0; i < numBuckets; i++) {
Collections.sort(buckets.get(i));
}
// Concatenate the sorted buckets back into the original array
List sortedArr = new ArrayList<>();
for (int i = 0; i < numBuckets; i++) {
sortedArr.addAll(buckets.get(i));
}
return sortedArr;
}
public static void main(String[] args) {
List arr = List.of(0.42, 0.32, 0.67, 0.25, 0.76, 0.88, 0.11, 0.43, 0.22);
int numBuckets = 3;
List sortedArr = bucketSort(arr, numBuckets);
System.out.println(sortedArr);
}
}

## Time and Space Complexity

The time complexity of bucket sort depends on the number of buckets and the sorting algorithm used to sort the individual buckets. Assuming that we use an efficient sorting algorithm like quicksort to sort the individual buckets, the time complexity of bucket sort can be expressed as:

- Best case: O(n+k), where n is the number of elements in the input array and k is the number of buckets

- Average case: O(n+k)

- Worst case: O(n^2), when all the elements are placed into a single bucket and that bucket needs to be sorted using a slow sorting algorithm like insertion sort

Note that the worst case only occurs if the range of the input values is very small and all the values fall into the same bucket.

The space complexity of bucket sort is O(n+k), where n is the number of elements in the input array and k is the number of buckets. This is because we need to allocate space for the buckets themselves, as well as for the output array that holds the sorted elements.

- Best case: O(n+k), where n is the number of elements in the input array and k is the number of buckets

- Average case: O(n+k)

- Worst case: O(n^2), when all the elements are placed into a single bucket and that bucket needs to be sorted using a slow sorting algorithm like insertion sort

Note that the worst case only occurs if the range of the input values is very small and all the values fall into the same bucket.

The space complexity of bucket sort is O(n+k), where n is the number of elements in the input array and k is the number of buckets. This is because we need to allocate space for the buckets themselves, as well as for the output array that holds the sorted elements.

## Advantages

- Bucket sort is a fast algorithm for sorting elements that are uniformly distributed across a range, such as floating-point numbers between 0 and 1.
- Bucket sort is relatively easy to implement and can be adapted to work with other data types besides floating-point numbers.
- Bucket sort can be faster than comparison-based sorting algorithms like quicksort and mergesort in some cases, especially when the input array is large and the range of values is small.
- Bucket sort can be parallelized easily, since each bucket can be sorted independently.

## Disadvantages

- Bucket sort is not suitable for sorting elements that are not uniformly distributed across a range, such as an array of integers with a few extremely large values.
- Bucket sort can be memory-intensive if the range of values is very large, since each bucket requires a certain amount of memory.
- Bucket sort can be slower than other sorting algorithms like quicksort and mergesort when the number of buckets is small and/or the range of values is large.
- The performance of bucket sort can be sensitive to the choice of bucket size and the sorting algorithm used to sort the individual buckets.