Tổng quan
Radix Sort sắp các số theo từng chữ số một, bắt đầu từ chữ số thấp nhất rồi tiến dần lên. Mỗi lượt là một phép chia thùng ổn định — thường là counting sort — và sau chữ số cuối cùng thì cả mảng đã đúng thứ tự.
Kết quả trông như ảo thuật: không lúc nào thuật toán so sánh hai số đầy đủ với nhau, vậy mà chúng vẫn ra đúng thứ tự. Thứ chuyển tiếp trật tự qua các lượt chính là tính ổn định. Vì mỗi lượt giữ nguyên thứ tự tương đối do lượt trước tạo ra, việc sắp theo hàng chục vẫn bảo toàn thứ tự hàng đơn vị bên trong từng nhóm.
Radix Sort hoạt động thế nào?
- Tìm giá trị lớn nhất để biết khóa dài nhất có bao nhiêu chữ số d.
- Bắt đầu từ chữ số thấp nhất — hàng đơn vị.
- Phân phối mọi phần tử vào các thùng theo chữ số đó, dùng một lượt ổn định để các chữ số bằng nhau giữ nguyên thứ tự sẵn có.
- Gom các thùng trở lại mảng theo thứ tự thùng, rồi chuyển sang chữ số kế tiếp.
- Lặp lại cho đủ d chữ số. Sau lượt của chữ số cao nhất, mảng đã sắp xong hoàn toàn.
Khi nào nên dùng?
- Khối lượng lớn số nguyên độ rộng cố định: mã định danh, mã bưu chính, mốc thời gian, địa chỉ IP coi như số 32 bit.
- Chuỗi độ dài cố định sắp theo từ điển, khi mỗi vị trí ký tự là một 'chữ số'.
- Sắp xếp trên bộ nhớ ngoài hoặc trong phần cứng, nơi mẫu truy cập cố định và không phụ thuộc dữ liệu quan trọng hơn hằng số nhân.
- Yếu khi khóa dài so với n — sắp một trăm số 20 chữ số nghĩa là hai mươi lượt để xếp một trăm phần tử.
Phân tích độ phức tạp
Thời gian là O(d · (n + b)) với d là số vị trí chữ số và b là cơ số, nên với độ rộng khóa cố định thì nó tuyến tính theo n. Cái d đó dễ bị bỏ qua: thực chất nó là log_b(giá trị lớn nhất), và đó là lý do radix sort không phải 'sắp xếp tuyến tính' nói chung, chỉ tuyến tính với khóa có độ rộng bị chặn. Bộ nhớ là O(n + b) cho các thùng và mảng kết quả.
Câu hỏi thường gặp
Vì sao lượt sắp theo từng chữ số bắt buộc phải ổn định?
Tính ổn định chính là toàn bộ cơ chế. Công sức bỏ ra ở các chữ số trước chỉ tồn tại được vì lượt sau không bao giờ xáo lại các phần tử có cùng chữ số hiện tại. Thay bằng một lượt không ổn định thì thuật toán cho ra kết quả vô nghĩa.
Vì sao lại bắt đầu từ chữ số thấp nhất?
Đi từ chữ số thấp nhất cho phép một dãy lượt duy nhất xử lý cả mảng, không cần đệ quy và không cần quản lý trạng thái. Bắt đầu từ chữ số cao nhất cũng được nhưng phải đệ quy riêng vào từng thùng, vì các nhóm trở thành bài toán con độc lập.
Cơ số lớn hơn có nhanh hơn không?
Chỉ tới một mức nào đó. Cơ số 256 cần một phần tư số lượt so với cơ số 10 cho khóa 32 bit, đổi lại 256 thùng. Đẩy cơ số cao hơn nữa thì lượt quét thùng cộng áp lực cache bắt đầu tốn hơn số lượt bạn tiết kiệm được.