Bucket Sort
Distribution – based sorting algorithms.
Example
[0.70, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.23, 0.68]
- bucket[1] = [0.17]
- bucket[2] = [0.21, 0.23, 0.26]
- bucket[3] = [0.39]
- bucket[6] = [0.68]
- bucket[7] = [0,70, 0.72]
- bucket[9] = [0.94]
Now, if we read from top to bottom:
[0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.70, 0.72, 0.94]
Hence, the data is Sorted.
If all elements fall into a single bucket, then traditional sorting algorithms must be used. The main advantage of Bucket Sort lies in distribution—if the data is distributed properly, sorting becomes very efficient.
Bucket Sort is mainly used when the data range is known. If the range is clear, Bucket Sort becomes easy to apply.
Time Complexity
Average Case: O(d * (n + k))
where k: number of buckets
- if the distribution is;
- each bucket has few elements
- sorting individual bucket is cheap
Worst Case: O(n2) all element in the same bucket
Space Complexity
O(n + k)
function bucketSort(arr) {
let n = arr.length;
let buckets = Array.from({ length: n}, () => []);
for(let x of arr){
let index = Math.floor(x * n)
buckets[index].push(x);
}
for(let bucket of buckets){
bucket.sort((a, b) => a - b);
}
let i = 0;
for(let bucket of buckets) {
for(let num of bucket) {
arr[i++] = num;
}
}
return arr;
}
const nums = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
console.log(bucketSort(nums));
def bucketSort(arr):
n = len(arr)
buckets = [[] for _ in range(n)]
for x in arr:
index = int(x * n)
buckets[index].append(x)
for bucket in buckets:
bucket.sort()
i = 0
for bucket in buckets:
for num in bucket:
arr[i] = num
i += 1
return arr
nums = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
print(bucketSort(nums))
import java.util.*;
public class BucketSort {
static double[] bucketSort(double[] arr) {
int n = arr.length;
List[] buckets = new ArrayList[n];
for (int i = 0; i < n; i++) {
buckets[i] = new ArrayList<>();
}
for (double x : arr) {
int index = (int)(x * n);
buckets[index].add(x);
}
for (List bucket : buckets) {
Collections.sort(bucket);
}
int i = 0;
for (List bucket : buckets) {
for (double num : bucket) {
arr[i++] = num;
}
}
return arr;
}
public static void main(String[] args) {
double[] nums = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
System.out.println(Arrays.toString(bucketSort(nums)));
}
}
#include <bits/stdc++.h>
using namespace std;
vector bucketSort(vector& arr) {
int n = arr.size();
vector> buckets(n);
for (double x : arr) {
int index = x * n;
buckets[index].push_back(x);
}
for (auto& bucket : buckets) {
sort(bucket.begin(), bucket.end());
}
int i = 0;
for (auto& bucket : buckets) {
for (double num : bucket) {
arr[i++] = num;
}
}
return arr;
}
int main() {
vector nums = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
bucketSort(nums);
for (double x : nums) cout << x << " ";
return 0;
}
#include <stdio.h>
#include <stdlib.h>
void bucketSort(double arr[], int n) {
double** buckets = (double**)malloc(n * sizeof(double*));
int* sizes = (int*)calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
buckets[i] = (double*)malloc(n * sizeof(double));
}
for (int i = 0; i < n; i++) {
int index = (int)(arr[i] * n);
buckets[index][sizes[index]++] = arr[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < sizes[i] - 1; j++) {
for (int k = j + 1; k < sizes[i]; k++) {
if (buckets[i][j] > buckets[i][k]) {
double temp = buckets[i][j];
buckets[i][j] = buckets[i][k];
buckets[i][k] = temp;
}
}
}
}
int idx = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < sizes[i]; j++) {
arr[idx++] = buckets[i][j];
}
}
}
int main() {
double nums[] = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
int n = sizeof(nums) / sizeof(nums[0]);
bucketSort(nums, n);
for (int i = 0; i < n; i++)
printf("%f ", nums[i]);
return 0;
}
using System;
using System.Collections.Generic;
using System.Linq;
class Program {
static double[] bucketSort(double[] arr) {
int n = arr.Length;
List[] buckets = new List[n];
for (int i = 0; i < n; i++) {
buckets[i] = new List();
}
foreach (double x in arr) {
int index = (int)(x * n);
buckets[index].Add(x);
}
foreach (var bucket in buckets) {
bucket.Sort();
}
int iIndex = 0;
foreach (var bucket in buckets) {
foreach (double num in bucket) {
arr[iIndex++] = num;
}
}
return arr;
}
static void Main() {
double[] nums = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
Console.WriteLine(string.Join(" ", bucketSort(nums)));
}
}
