การนำ Bucket Sort ไปใช้ใน JavaScript

ภาพรวม

Bucket Sort เป็นอัลกอริทึมการจัดเรียงที่กระจายข้อมูลเข้า "ถัง" (Buckets) ตามช่วงค่า แล้วจัดเรียงในแต่ละถังแยกกัน แล้วรวมกัน เหมาะกับข้อมูลที่กระจายตัวสม่ำเสมอ (Uniform Distribution)

ขั้นตอนอัลกอริทึม

1. หาค่า Min และ Max ของอาร์เรย์
2. สร้าง Buckets ตามจำนวนที่กำหนด (Bucket Size)
3. กระจายข้อมูลเข้า Buckets ตามช่วงค่า
4. จัดเรียงข้อมูลในแต่ละ Bucket (ใช้ Insertion Sort)
5. รวม 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 minValue = arr[0];
  let maxValue = arr[0];
  const bucketSize = 5;
  
  // หา Min/Max
  arr.forEach(val => {
    if (val < minValue) minValue = val;
    else if (val > maxValue) maxValue = val;
  });
  
  // สร้าง Buckets
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  const allBuckets = Array.from({ length: bucketCount }, () => []);
  
  // กระจายข้อมูล
  arr.forEach(val => {
    const bucketIndex = Math.floor((val - minValue) / bucketSize);
    allBuckets[bucketIndex].push(val);
  });
  
  // จัดเรียงแต่ละ Bucket และรวม
  arr.length = 0;
  allBuckets.forEach(bucket => {
    insertionSort(bucket);
    bucket.forEach(el => arr.push(el));
  });
  
  return arr;
};

const insertionSort = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    let temp = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
  return arr;
};

console.log(bucketSort(arr));

ผลลัพธ์

[1, 4, 4, 6, 7, 32, 34, 34, 65, 78, 879, 6767]

Complexity Analysis

k = จำนวน Buckets, n = จำนวนข้อมูล

เมื่อไหร่ควรใช้ Bucket Sort

• ข้อมูลกระจายตัวสม่ำเสมอ (Uniform Distribution)
• ทราบช่วงค่า Min/Max ล่วงหน้า
• ข้อมูลเป็น Floating Point Numbers
• ต้องการ Stable Sort

การปรับแต่ง Bucket Size

// Bucket Size แบบ Dynamic (Square Root Rule)
const optimalBucketSize = (arr) => {
  const range = Math.max(...arr) - Math.min(...arr);
  return Math.max(1, Math.floor(range / Math.sqrt(arr.length)));
};

เปรียบเทียบกับอัลกอริทึมอื่น

• vs Quick Sort: Bucket Sort เร็วกว่าสำหรับ Uniform Data แต่ต้องการพื้นที่เพิ่ม
• vs Counting Sort: Bucket Sort ใช้ได้กับ Float, Counting Sort ใช้ได้เฉพาะ Integer
• vs Radix Sort: Radix Sort ดีกว่าสำหรับ Integer ขนาดใหญ่