Bucket Sort ทำงานโดยแยกอาร์เรย์ของขนาด n ออกเป็น k บัคเก็ตซึ่งมีช่วงค่าขององค์ประกอบเฉพาะ
จากนั้น ที่เก็บข้อมูลเหล่านี้จะถูกจัดเรียงโดยใช้อัลกอริธึมการจัดเรียง ซึ่งสามารถเลือกได้ตามขนาดอินพุตที่คาดไว้
เราสามารถอธิบายอัลกอริทึมนี้ได้ดังนี้ -
อัลกอริทึม:
Create the initial bucketSort function Create variables for i, min, max, and bucket size Find min and max value Create amount of buckets Push values to correct buckets Sort buckets
ตัวอย่าง
รหัสสำหรับสิ่งนี้จะเป็น −
const arr = [32, 6, 34, 4, 78, 1, 6767, 4, 65, 34, 879, 7];
const bucketSort = arr => {
if (arr.length === 0) {
return arr;
}
let i,
minValue = arr[0],
maxValue = arr[0],
bucketSize = 5;
arr.forEach(function (currentVal) {
if (currentVal < minValue) {
minValue = currentVal;
} else if (currentVal > maxValue) {
maxValue = currentVal;
}
})
let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
let allBuckets = new Array(bucketCount);
for (i = 0; i < allBuckets.length; i++) {
allBuckets[i] = [];
}
arr.forEach(function (currentVal) {
allBuckets[Math.floor((currentVal - minValue) / bucketSize)].push(currentVal);
});
arr.length = 0;
allBuckets.forEach(function(bucket) {
insertion(bucket);
bucket.forEach(function (element) {
arr.push(element)
});
});
return arr;
}
const insertion = arr => {
let length = arr.length;
let i, j;
for(i = 1; i < length; i++) {
let temp = arr[i];
for(j = i - 1; j >= 0 && arr[j] > temp; j--) {
arr[j+1] = arr[j];
}
arr[j+1] = temp;
}
return arr;
};
console.log(bucketSort(arr)); ผลลัพธ์
เอาต์พุตในคอนโซล −
[ 1, 4, 4, 6, 7, 32, 34, 34, 65, 78, 879, 6767 ]
