Bucket Sort

Bucket Sort :

Author(s) : Joseph J. Aiken and Robert Sedgewick Date : 1960s

Bucket 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

Python JavaScript Java Go C
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]);
}
light dark