Sắp xếp cơ số¶

Phần trước đã giới thiệu sắp xếp đếm, vốn phù hợp khi số lượng phần tử \(n\) lớn nhưng phạm vi giá trị \(m\) nhỏ. Giả sử chúng ta cần sắp xếp \(n = 10^6\) mã số học sinh, mỗi mã số là một số có 8 chữ số. Khi đó, phạm vi giá trị \(m = 10^8\) là rất lớn. Việc sử dụng sắp xếp đếm sẽ đòi hỏi một lượng bộ nhớ lớn, trong khi sắp xếp cơ số có thể tránh được vấn đề này.

Sắp xếp cơ số dựa trên cùng ý tưởng cốt lõi với sắp xếp đếm: nó cũng sắp xếp bằng cách đếm số lần xuất hiện. Trên cơ sở này, sắp xếp cơ số tận dụng mối quan hệ vị trí giữa các chữ số và sắp xếp chúng theo từng chữ số một để thu được kết quả cuối cùng.

Quy trình thuật toán¶

Lấy dữ liệu mã số học sinh làm ví dụ, giả sử chữ số hàng thấp nhất là chữ số thứ \(1\) và chữ số hàng cao nhất là chữ số thứ \(8\). Quy trình của sắp xếp cơ số được thể hiện trong hình dưới đây.

Khởi tạo chữ số \(k = 1\).
Thực hiện "sắp xếp đếm" trên chữ số thứ \(k\) của các mã số học sinh. Sau khi hoàn thành, dữ liệu sẽ được sắp xếp từ nhỏ đến lớn theo chữ số thứ \(k\).
Tăng \(k\) lên \(1\), sau đó quay lại bước 2. và tiếp tục lặp lại cho đến khi tất cả các chữ số đều được sắp xếp, tại thời điểm đó quy trình kết thúc.

Tiếp theo, hãy cùng xem mã nguồn. Đối với một số \(x\) trong hệ cơ số \(d\), chữ số thứ \(k\) của nó \(x_k\) có thể được xác định bằng công thức sau:

\[ x_k = \lfloor\frac{x}{d^{k-1}}\rfloor \bmod d \]

Trong đó, \(\lfloor a \rfloor\) ký hiệu phép làm tròn xuống số thực dấu phẩy động \(a\), và \(\bmod \: d\) ký hiệu phép chia lấy dư cho \(d\). Đối với dữ liệu mã số học sinh, \(d = 10\) và \(k \in [1, 8]\).

Ngoài ra, chúng ta cần sửa đổi một chút mã nguồn của sắp xếp đếm để nó thực hiện sắp xếp dựa trên chữ số thứ \(k\) của số đó:

[file]{radix_sort}-[class]{}-[func]{radix_sort}

Tại sao lại bắt đầu sắp xếp từ chữ số hàng thấp nhất?

Trong các lượt sắp xếp liên tiếp, lượt sắp xếp sau sẽ ghi đè lên kết quả của lượt sắp xếp trước đó. Ví dụ, nếu lượt sắp xếp đầu tiên cho kết quả \(a < b\) nhưng lượt thứ hai cho kết quả \(a > b\), thì kết quả của lượt thứ hai sẽ được giữ lại. Vì các chữ số ở hàng cao hơn có độ ưu tiên cao hơn các chữ số ở hàng thấp hơn, chúng ta nên sắp xếp các chữ số ở hàng thấp trước, sau đó mới đến các chữ số ở hàng cao.

Đặc điểm của thuật toán¶

So với sắp xếp đếm, sắp xếp cơ số phù hợp cho các phạm vi giá trị lớn hơn, nhưng chỉ khi dữ liệu có thể được biểu diễn dưới dạng các số có số chữ số cố định và số lượng chữ số đó không quá lớn. Ví dụ, số thực dấu phẩy động không thực sự phù hợp với sắp xếp cơ số vì số lượng chữ số \(k\) có thể quá lớn, có khả năng dẫn đến độ phức tạp thời gian \(O(nk) \gg O(n^2)\).

Độ phức tạp thời gian là \(O(nk)\), sắp xếp không thích ứng: Giả sử số lượng phần tử là \(n\), các giá trị được biểu diễn trong hệ cơ số \(d\), và số lượng chữ số tối đa là \(k\). Sắp xếp đếm trên một chữ số mất thời gian \(O(n + d)\), do đó việc sắp xếp toàn bộ \(k\) chữ số sẽ mất thời gian \(O((n + d)k)\). Trong thực tế, \(d\) và \(k\) thường tương đối nhỏ, vì vậy độ phức tạp thời gian tổng thể sẽ tiệm cận \(O(n)\).
Độ phức tạp không gian là \(O(n + d)\), sắp xếp không tại chỗ: Tương tự như sắp xếp đếm, sắp xếp cơ số yêu cầu các mảng phụ trợ res và counter có độ dài tương ứng là \(n\) và \(d\).
Sắp xếp ổn định: Khi sắp xếp đếm ổn định, sắp xếp cơ số cũng ổn định; khi sắp xếp đếm không ổn định, sắp xếp cơ số không thể đảm bảo kết quả sắp xếp chính xác.