What is Bucket Sort
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.
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);
}
}