bucket Sort Algorithm
The bucket sort algorithm is a sorting technique that works by distributing the elements of an array into a number of "buckets" based on their values, followed by sorting each bucket individually. This method is particularly useful for sorting data that is uniformly distributed over a range of values, as it can provide efficient sorting with minimal comparisons. The main idea behind bucket sort is to divide the data set into a series of smaller, more manageable groups, which can be sorted independently, and then combined to form the final sorted result.
To implement the bucket sort algorithm, first, determine the range of the input data and the number of buckets to be used. Each bucket represents a range of values within the overall range of the data. Then, iterate through the input array, placing each element into the appropriate bucket based on its value. Once all elements have been added to their respective buckets, sort each bucket individually using any suitable sorting algorithm, such as insertion sort or quick sort. Finally, concatenate the sorted buckets together to obtain the fully sorted array. The efficiency of the bucket sort algorithm largely depends on the distribution of the input data and the choice of the sorting algorithm used for sorting individual buckets.
/*
Wikipedia says: Bucket sort, or bin sort, is a sorting algorithm that works by distributing the
elements of an array into a number of buckets. Each bucket is then sorted individually, either using
a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a
distribution sort, and is a cousin of radix sort in the most to least significant digit flavour.
Bucket sort is a generalization of pigeonhole sort. Bucket sort can be implemented with comparisons
and therefore can also be considered a comparison sort algorithm. The computational complexity estimates
involve the number of buckets.
Time Complexity of Solution:
Best Case O(n); Average Case O(n); Worst Case O(n)
*/
function bucketSort (list, size) {
if (undefined === size) {
size = 5
}
if (list.length === 0) {
return list
}
let min = list[0]
let max = list[0]
// find min and max
for (let iList = 0; iList < list.length; iList++) {
if (list[iList] < min) {
min = list[iList]
} else if (list[iList] > max) {
max = list[iList]
}
}
// how many buckets we need
const count = Math.floor((max - min) / size) + 1
// create buckets
const buckets = []
for (let iCount = 0; iCount < count; iCount++) {
buckets.push([])
}
// bucket fill
for (let iBucket = 0; iBucket < list.length; iBucket++) {
const key = Math.floor((list[iBucket] - min) / size)
buckets[key].push(list[iBucket])
}
const sorted = []
// now sort every bucket and merge it to the sorted list
for (let iBucket = 0; iBucket < buckets.length; iBucket++) {
const arr = buckets[iBucket].sort()
for (let iSorted = 0; iSorted < arr.length; iSorted++) {
sorted.push(arr[iSorted])
}
}
return sorted
}
// Testing
const arrOrignal = [5, 6, 7, 8, 1, 2, 12, 14]
// > bucketSort(arrOrignal)
// [1, 2, 5, 6, 7, 8, 12, 14]
// Array before Sort
console.log(arrOrignal)
const arrSorted = bucketSort(arrOrignal)
// Array after sort
console.log(arrSorted)
