Skip to content

Commit b596741

Browse files
authored
Merge pull request vJechsmayr#104 from MariaLuize/BucketSort
Implementation of BucketSort in JS
2 parents 1cd4ef3 + ae9dd22 commit b596741

1 file changed

Lines changed: 63 additions & 0 deletions

File tree

‎SortingAlgorithms/BucketSort.js‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
//Language: Javascript
2+
//Author: Maria Luize
3+
//Github: https://github.com/MariaLuize
4+
5+
function insertSort(arr) {
6+
const len = arr.length;
7+
8+
for(let i = 1; i < len; i++) {
9+
let temp = arr[i];
10+
for(let j = i - 1; j >= 0 && arr[j] > temp; j--) {
11+
arr[j+1] = arr[j];
12+
}
13+
arr[j+1] = temp;
14+
}
15+
16+
return arr;
17+
}
18+
19+
// Bucket sort itself
20+
function bucketSort(arr, bucketSize) {
21+
if (arr.length === 0) {
22+
return arr;
23+
}
24+
25+
var i,
26+
minValue = arr[0],
27+
maxValue = arr[0],
28+
bucketSize = bucketSize || 5;
29+
30+
// Setting min and max values
31+
arr.forEach(function (currentVal) {
32+
if (currentVal < minValue) {
33+
minValue = currentVal;
34+
} else if (currentVal > maxValue) {
35+
maxValue = currentVal;
36+
}
37+
})
38+
39+
// Initializing buckets
40+
const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
41+
let allBuckets = new Array(bucketCount);
42+
43+
for (i = 0; i < allBuckets.length; i++) {
44+
allBuckets[i] = [];
45+
}
46+
47+
// Pushing values
48+
arr.forEach((currentVal) => {
49+
allBuckets[Math.floor((currentVal - minValue) / bucketSize)].push(currentVal);
50+
});
51+
52+
// Sorting buckets
53+
arr.length = 0;
54+
55+
allBuckets.forEach((bucket) => {
56+
insertionSort(bucket);
57+
bucket.forEach((element) =>{
58+
arr.push(element)
59+
});
60+
});
61+
62+
return arr;
63+
}

0 commit comments

Comments
 (0)