Radix Sort (การจัดเรียงแบบราดิกซ์)

Radix Sort เป็นอัลกอริทึมจัดเรียงแบบ Non-comparison (ไม่เปรียบเทียบ) จัดเรียงจำนวนเต็มโดยประมวลผลทีละ หลัก (Digit) เริ่มจากหลักหน่วย (LSD) หรือหลักสูงสุด (MSD) ใช้ Counting Sort เป็น Subroutine

ความซับซ้อน (Complexity)

แนวคิดการทำงาน (LSD - Least Significant Digit)

1. หาจำนวนหลักสูงสุด maxDigits
2. สำหรับแต่ละหลัก (หน่วย, สิบ, ร้อย, ...):
3. ใช้ Counting Sort จัดเรียงตามหลักนั้น (Stable)
4. ใช้ base = 10 สำหรับทศนิยม

ตัวอย่างข้อมูล

Input:  802 630 20 745 52 300 612 932 78 187
Output: 20 52 78 187 300 612 630 745 802 932

อัลกอริทึม (Pseudocode)

radixSort(array, size, maxDigit)
  for digit = 0 to maxDigit-1:
    m = 10^(digit+1)
    p = 10^digit
    pockets[0..9] = empty lists

    for j = 0 to size-1:
      temp = array[j] % m
      index = temp / p
      pockets[index].append(array[j])

    count = 0
    for j = 0 to 9:
      while pockets[j] not empty:
        array[count++] = pockets[j].pop_front()

ตัวอย่างโค้ด C++

#include <iostream>
#include <list>
#include <cmath>
using namespace std;

void radixSort(int *arr, int n, int maxDigits) {
    for (int d = 0; d < maxDigits; d++) {
        int m = pow(10, d+1);
        int p = pow(10, d);
        list<int> pocket[10];

        // Distribute
        for (int j = 0; j < n; j++) {
            int temp = arr[j] % m;
            int idx = temp / p;
            pocket[idx].push_back(arr[j]);
        }

        // Gather
        int count = 0;
        for (int j = 0; j < 10; j++) {
            while (!pocket[j].empty()) {
                arr[count++] = pocket[j].front();
                pocket[j].pop_front();
            }
        }
    }
}

void display(int *array, int size) {
    for (int i = 0; i < size; i++) cout << array[i] << " ";
    cout << endl;
}

int main() {
    int n, maxDigits;
    cin >> n >> maxDigits;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    cout << "Before: "; display(arr, n);
    radixSort(arr, n, maxDigits);
    cout << "After: "; display(arr, n);
}

คุณสมบัติสำคัญ

• Stable: ต้องใช้ Stable Sort เป็น Subroutine (Counting Sort)
• Non-comparison: ไม่เปรียบเทียบค่าโดยตรง
• Linear Time: O(n) เมื่อหลักคงที่ (k = constant)
• Not In-place: ต้องการพื้นที่ O(n+k)

LSD vs MSD

• LSD (Least Significant Digit): เริ่มหลักหน่วย → ง่าย, Stable, เหมาะ Fixed-width
• MSD (Most Significant Digit): เริ่มหลักสูงสุด → ใช้ Recursion, เหมาะ Variable-length (Strings)

การประยุกต์ใช้

• จัดเรียงจำนวนเต็ม 32/64-bit (d = 10 หรือ 20 หลัก base 10)
• จัดเรียง String (MSD Radix Sort)
• Suffix Array Construction
• GPU Sorting (Parallelizable)