Bucket Sort
Bucket Sort :
Author(s) : Joseph J. Aiken and Robert Sedgewick Date : 1960sBucket sort is a sorting technique that divides the input data into a fixed number of buckets (sub-arrays). Each bucket is then sorted individually using a suitable sorting algorithm like insertion sort. Finally, the sorted buckets are concatenated to form the final sorted output. The efficiency of bucket sort heavily relies on choosing the appropriate number of buckets and a sorting algorithm for the buckets. It can be very efficient for data with a uniform distribution within a specific range. However, for skewed distributions or large ranges, bucket sort might require adjustments or become less effective.
Time Complexity | O(n + k) |
Best Case | O(n + k) |
Worst Case | O(n² * k) |
Space Complexity | O(n + k) |
Stable | Yes |
Code Integration:
* the code might contain some bugs or may not work correctly
def bucket_sort(arr):
max_value = max(arr)
bucket_size = int(max_value / 10) + 1 # Assuming 10 buckets for simplicity
buckets = [[] for _ in range(bucket_size)]
for i in arr:
index = i // bucket_size
buckets[index].append(i)
for i in range(bucket_size):
buckets[i].sort()
result = []
for bucket in buckets:
result.extend(bucket)
return result
# Test array
arr = [8, 3, 2, 7, 4, 6, 9]
print('Sorted array is:', bucket_sort(arr))
function bucketSort(arr) {
let max_value = Math.max(...arr);
let bucket_size = Math.floor(max_value / 10) + 1; // Assuming 10 buckets for simplicity
let buckets = Array(bucket_size).fill([]);
for (let i of arr) {
let index = Math.floor(i / bucket_size);
buckets[index].push(i);
}
for (let i = 0; i < bucket_size; i++) {
buckets[i].sort((a, b) => a - b);
}
let result = [];
for (let bucket of buckets) {
result.push(...bucket);
}
return result;
}
// Test array
let arr = [8, 3, 2, 7, 4, 6, 9];
console.log('Sorted array is:', bucketSort(arr));
public static int[] bucketSort(int[] arr) {
int max_value = Integer.MIN_VALUE;
for (int i : arr) {
max_value = Math.max(max_value, i);
}
int bucket_size = (max_value / 10) + 1; // Assuming 10 buckets for simplicity
List<Integer>[] buckets = new List[bucket_size];
for (int i = 0; i < bucket_size; i++) {
buckets[i] = new ArrayList<>();
}
for (int i : arr) {
int index = i / bucket_size;
buckets[index].add(i);
}
for (int i = 0; i < bucket_size; i++) {
Collections.sort(buckets[i]); // Sort individual buckets using Collections.sort
}
int index = 0;
int[] sortedArr = new int[arr.length];
for (List<Integer> bucket : buckets) {
for (int value : bucket) {
sortedArr[index++] = value;
}
}
return sortedArr;
}
// Test array
int[] arr = {8, 3, 2, 7, 4, 6, 9};
System.out.println('Sorted array is: ' + Arrays.toString(bucketSort(arr)));
func bucketSort(arr []int, n int) []int {
bucketSize := n / 10 // Assuming 10 buckets for simplicity
buckets := make([][]int, bucketSize)
for _, val := range arr {
index := val / bucketSize
buckets[index] = append(buckets[index], val)
}
for i := range buckets {
sort.Ints(buckets[i]) // Sort individual buckets (using in-built sort)
}
result := []int{}
for _, bucket := range buckets {
result = append(result, bucket...)
}
return result
}
// Test array
arr := []int{8, 3, 2, 7, 4, 6, 9}
fmt.Println('Sorted array is:', bucketSort(arr, len(arr)))
void bucket_sort(int arr[], int n) {
int max_value = arr[0];
for (int i = 1; i < n; i++) {
max_value = max(max_value, arr[i]);
}
int bucket_size = n / 10; // Assuming 10 buckets for simplicity
int i, j;
int *buckets[bucket_size];
for (i = 0; i < bucket_size; ++i) {
buckets[i] = (int *)malloc(n * sizeof(int)); // Allocate memory for each bucket
buckets[i][0] = 0; // Initialize bucket size to 0
}
for (i = 0; i < n; i++) {
int index = arr[i] / bucket_size;
buckets[index][++buckets[index][0]] = arr[i]; // Increment size and insert element
}
for (i = 0; i < bucket_size; i++) {
qsort(buckets[i], buckets[i][0], sizeof(int), compare); // Sort individual buckets
free(buckets[i]); // Free allocated memory for each bucket
}
i = 0;
for (j = 0; j < bucket_size; j++) {
for (int k = 0; k < buckets[j][0]; k++) {
arr[i++] = buckets[j][k + 1];
}
}
}
// Helper function for qsort comparison (assuming qsort is available)
int compare(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
// Test array
int arr[] = {8, 3, 2, 7, 4, 6, 9};
int n = sizeof(arr) / sizeof(arr[0]);
bucket_sort(arr, n);
printf('Sorted array is: ');
for (int i = 0; i < n; i++) {
printf('%d ', arr[i]);
}