Radix Sort ใน JavaScript

Radix Sort คืออะไร

Radix Sort เป็นอัลกอริทึมจัดเรียงที่ ไม่เปรียบเทียบ (Non-comparative) จัดกลุ่มตัวเลขตามหลัก (Digit) ตั้งแต่หลักหน่วย สิบ ร้อย... ใช้ Counting Sort เป็น subroutine

คุณสมบัติ

• Time: O(d × (n + b)) โดย d = จำนวนหลัก, n = จำนวนข้อมูล, b = base (ปกติ 10)
• Space: O(n + b)
• Stable Sort (รักษาลำดับเดิมของค่าเท่ากัน)
• เหมาะสำหรับจำนวนเต็ม (Integers)

โค้ดตัวอย่าง (LSD - Least Significant Digit)

const arr = [45, 2, 56, 2, 5, 6, 34, 1, 56, 89, 33];

const radixSort = (arr = []) => {
  const base = 10;
  let divider = 1;
  let maxVal = Number.NEGATIVE_INFINITY;
  
  // หาค่าสูงสุดและจัดเรียงทีละหลัก
  while (divider === 1 || divider <= maxVal) {
    const buckets = [...Array(10)].map(() => []);
    
    for (let val of arr) {
      const digit = Math.floor((val / divider) % base);
      buckets[digit].push(val);
      maxVal = val > maxVal ? val : maxVal;
    }
    
    // รวม buckets กลับ
    arr = [].concat(...buckets);
    divider *= base;
  }
  return arr;
};

console.log(radixSort(arr));

ผลลัพธ์

[1, 2, 2, 5, 6, 33, 34, 45, 56, 56, 89]

วิธี MSD (Most Significant Digit) - Recursive

const radixSortMSD = (arr, digit = 0) => {
  if (arr.length <= 1) return arr;
  
  const buckets = [...Array(10)].map(() => []);
  let maxLen = 0;
  
  for (let num of arr) {
    const str = num.toString();
    maxLen = Math.max(maxLen, str.length);
    const d = str.length > digit ? parseInt(str[str.length - 1 - digit]) : 0;
    buckets[d].push(num);
  }
  
  if (digit >= maxLen) return arr.flat();
  
  return buckets.flatMap(bucket => radixSortMSD(bucket, digit + 1));
};

รองรับตัวเลขลบ

const radixSortWithNegatives = (arr) => {
  const negatives = arr.filter(x => x < 0).map(x => -x);
  const positives = arr.filter(x => x >= 0);
  
  return [...radixSort(negatives).reverse().map(x => -x), ...radixSort(positives)];
};

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

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

• จำนวนเต็มจำนวนมาก (Millions) ที่มีช่วงค่ากว้าง
• ต้องการ Stable Sort
• ประสิทธิภาพดีกว่า Comparison sorts เมื่อ d < log n