Learn what is a bucket sort algorithm and how to implement it in Javascript.
List of sorting algorithms
- Bubble sort algorithm in javascript
- Insertion sort algorithm in javascript
- Selection sort in javascript
- Merge sort in javascript
- Quick sort in javascript
- Counting sort in javascript
- Radix sort in javascript
- Shell sort in javascript
- Heap sort in javascript
What is bucket sort?
Bucket sort or bin sort is a distribution sort, a generalization of pigeonhole sort, and is a cousin of radix sort in the most-to-least significant digit flavor.
Bucket sort is a sorting technique that sorts the elements by first distributing or grouping the elements into several groups called buckets. Then sort the elements inside each bucket by using any other sorting algorithm or recursively calling the same algorithm.
The process of bucket sort can be understood as a scatter-gather approach. The elements are first scattered into buckets then the elements of buckets are sorted. Finally, the elements are gathered in order.
How bucket sort works?
1. Suppose you are given an array of [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51].
2. Now create a temporary which can contain the buckets with the range of element.
3. Then sort these buckets individually.
4. Now merge these sorted buckets to form the sorted array.
Like its cousin Radix sort, bucket sort also uses the element as the index for grouping, thus it cannot work on other data structure, we can sort the array of characters or string by using a hashing method where we convert the value to the numeric index.
bucketSort()
create N buckets each of which can hold a range of values
for all the buckets
initialize each bucket with 0 values
for all the buckets
put elements into buckets matching the range
for all the buckets
sort elements in each bucket
gather elements from each bucket
end bucketSort
As we group elements in the range that is why bucket sort is most suitable for sorting an array of floating values or input is uniformly distributed over a range.
Bucket sort algorithm on an array of positive floating values.
const bucketSort = (arr, n = arr.length) => {
//Create a bucket array
let bucket = new Array(n);
//Add bucket group
for(let i = 0; i < n; i++){
bucket[i] = [];
}
//Add the elements in a same range in bucket
for(let i = 0; i < n; i++){
let bucketIndex = Math.floor(arr[i]) * n;
bucket[bucketIndex].push(arr[i]);
}
//Sort each bucket separately
for(let i = 0; i < n; i++){
bucket[i].sort();
}
// Get the sorted array
let index = 0;
for (let i = 0; i < n; i++) {
for (let j = 0, size = bucket[i].length; j < size; j++) {
arr[index++] = bucket[i][j];
}
}
}
Input: const arr = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]; bucketSort(arr); console.log(arr); Output: [0.32, 0.33, 0.37, 0.42, 0.47, 0.51, 0.52
Bucket sort algorithm on an array of negative floating values.
To sort the negative values we will have to add a additional wrapper. This is how it works.
- Separate the negative and positive values into two different arrays.
- While storing the negative values convert it to positive by multiplying them with -1.
- Sort these two arrays separately.
- And then merge them to form the sorted array, while merging add the negative values in reverse order by converting them back to negative and after that add the positive values.
const bucketSort = (arr, n = arr.length) => {
//Create a bucket array
let bucket = new Array(n);
//Add bucket group
for(let i = 0; i < n; i++){
bucket[i] = [];
}
//Add the elements in a same range in bucket
for(let i = 0; i < n; i++){
let bucketIndex = Math.floor(arr[i]) * n;
bucket[bucketIndex].push(arr[i]);
}
//Sort each bucket separately
for(let i = 0; i < n; i++){
bucket[i].sort();
}
// Get the sorted array
let index = 0;
for (let i = 0; i < n; i++) {
for (let j = 0, size = bucket[i].length; j < size; j++) {
arr[index++] = bucket[i][j];
}
}
}
const sortMixed = (arr, n = arr.length) => {
const neg = [];
const pos = [];
//Group the positive and negative values
for(let i = 0; i < n; i++){
if(arr[i] < 0){
neg.push(-1 * arr[i]);
}else{
pos.push(arr[i]);
}
}
//sort the group
bucketSort(neg);
bucketSort(pos);
// First store elements of Neg[] array
// by converting into -ve
for (let i = 0; i < neg.length; i++){
arr[i] = -1 * neg[ neg.length - 1 - i];
}
// store +ve element
for(let j = neg.length; j < n; j++) {
arr[j] = pos[j - neg.length];
}
}
Input: const negArr = [-0.897, 0.565, 0.656, -0.1234, 0, 0.3434]; sortMixed(negArr); console.log(negArr); Output: [-0.897, -0.1234, 0, 0.3434, 0.565, 0.656]
Time complexity
| Worst | Average | Best |
|---|---|---|
| O(n ^ 2) | O(n) | O(n+k) |
Worst Case: O(n^2).
If the elements in the array in close range then there is chance that they are placed in same bucket. This may cause some buckets to have more elements than others.
It makes the complexity dependent upon the sorting algorithm we are using to sort the elements of the bucket.
The worst-case occurs we the elements in the bucket are in reverse order and if Insertion sort is used then time complexity would be O(n ^ 2).
Best case: O(n+k).
It works when the elements are uniformly distributed in the buckets with an almost equal number of elements in each bucket.
The complexity becomes even better when the elements inside each bucket are already sorted.
If insertion sort is used to sort elements of a bucket then the overall complexity in the best case will be linear ie. O(n+k). O(n) is the complexity for making the buckets and O(k) is the complexity for sorting the elements of the bucket using algorithms having linear time complexity at the best case.
Average case: O(n).
It occurs when the elements are distributed randomly in the array. Even if the elements are not distributed uniformly, bucket sort runs in linear time. It holds true until the sum of the squares of the bucket sizes is linear in the total number of elements.
Space complexity
The space complexity of Bucket Sort is O(n ^ 2). Because we create buckets of the same length and each bucket has a sub bucket of the same length.