Cách Giải Sắp Xếp Theo Cơ Số (Radix Sort), Dể Hiểu
Thuật toán Sắp Xếp Theo Cơ Số được phát minh vào năm 1887 bởi nhà toán học Hermann Hollerith, người đã sáng chế ra máy tính thẻ đục lỗ để xử lý dữ liệu trong cuộc điều tra dân số Mỹ. Ông phát triển thuật toán này nhằm tối ưu hóa quy trình phân loại thẻ đục lỗ, cho phép sắp xếp dữ liệu một cách hiệu quả hơn bằng cách xử lý từng chữ số từ ít quan trọng đến quan trọng nhất.
Định Nghĩa
Sắp Xếp Theo Cơ Số (Radix Sort) là một thuật toán sắp xếp không dựa trên so sánh từng phần tử như các thuật toán sắp xếp thông thường (như Sắp Xếp Nổi Bọt, Sắp Xếp Nhanh). Thay vào đó, nó sắp xếp các số bằng cách xử lý từng chữ số theo thứ tự từ ít quan trọng nhất đến quan trọng nhất.
Thuật toán này áp dụng đặc biệt tốt cho dữ liệu dạng số nguyên hoặc chuỗi có độ dài cố định. Điều này giúp Sắp Xếp Theo Cơ Số nổi bật trong các trường hợp cần sắp xếp nhanh một lượng lớn số có cùng kích cỡ hoặc dạng.
Kỹ thuật này thường sử dụng phương pháp đếm và nhóm các số vào các “bucket” (xô) dựa trên từng chữ số. Bằng cách này, Sắp Xếp Theo Cơ Số sắp xếp mà không cần so sánh trực tiếp từng phần tử với nhau, giảm thiểu thời gian xử lý trong các trường hợp cụ thể.
Nói cách khác, Sắp Xếp Theo Cơ Số sắp xếp các số một cách hệ thống và thứ tự bằng cách “nhìn” vào từng chữ số, từng bước một, thay vì so sánh và hoán đổi toàn bộ số như một khối thống nhất.
Cách Giải
Thuật toán Sắp Xếp Theo Cơ Số hoạt động trên nguyên tắc sắp xếp theo từng chữ số từ ít quan trọng đến quan trọng nhất. Sau đây là cách giải chi tiết:
- Bắt đầu với chữ số ít quan trọng nhất (chữ số ngoài cùng bên phải).
- Sắp xếp các giá trị dựa trên chữ số đang được xem xét. Đưa các giá trị vào đúng “xô” dựa trên chữ số đó, sau đó gom các giá trị lại thành một mảng sắp xếp tạm thời.
- Tiếp tục sang chữ số kế tiếp và lặp lại quy trình trên, tiếp tục cho đến khi đã xét xong tất cả các chữ số.
Bạn thấy đó, quá trình này là sự lặp đi lặp lại, xử lý từng chữ số cho đến khi toàn bộ mảng đã được sắp xếp hoàn chỉnh.
Để dể hình dung hơn, bạn có thể xem diễn họa của thuật toán tại đây: https://www.w3schools.com/dsa/dsa_algo_radixsort.php
Triển Khai
Để triển khai thuật toán Sắp Xếp Theo Cơ Số, chúng ta cần:
- Một mảng chứa các số nguyên không âm cần được sắp xếp.
- Một mảng hai chiều với chỉ số từ 0 đến 9 để chứa các giá trị theo chữ số cơ số hiện tại đang xét.
- Một vòng lặp để lấy các giá trị từ mảng chưa sắp xếp và đặt chúng vào đúng vị trí trong mảng hai chiều của các chữ số cơ số.
- Một vòng lặp để đưa các giá trị từ mảng cơ số trở lại mảng ban đầu.
- Một vòng lặp bên ngoài chạy nhiều lần bằng số chữ số trong giá trị lớn nhất.
Mã TypeScript sẽ trông như sau:
import { expect } from 'jsr:@std/expect';
function radixSort(nums: number[]): number[] {
// Nếu mảng chỉ có 1 phần tử hoặc ít hơn, trả về mảng vì không cần sắp xếp
if (nums.length <= 1) return nums;
// Xác định số chữ số tối đa trong các số của mảng
const maxDigits = getMaxDigits(nums);
// Vòng lặp bên ngoài chạy số lần bằng số chữ số của giá trị lớn nhất
for (let k = 0; k < maxDigits; k++) {
// Tạo một mảng hai chiều gồm 10 mảng con, mỗi mảng sẽ giữ các giá trị có cùng chữ số ở vị trí đang xét
const buckets: number[][] = new Array(10).fill(0).map(() => []);
// Vòng lặp đưa các giá trị từ mảng chưa sắp xếp vào vị trí đúng trong mảng hai chiều (theo chữ số đang xét)
for (let i = 0; i < nums.length; i++) {
// Lấy chữ số ở vị trí đang xét của phần tử hiện tại
const digit = getDigit(nums[i], k);
// Đưa phần tử vào bucket tương ứng với chữ số vừa lấy được
buckets[digit].push(nums[i]);
}
// Gom các phần tử từ mảng hai chiều về lại mảng ban đầu
nums = buckets.flat();
}
// Trả về mảng đã được sắp xếp
return nums;
}
// Hàm lấy số chữ số tối đa của các số trong mảng
function getMaxDigits(nums: number[]): number {
let maxDigits = 0;
for (const num of nums) {
maxDigits = Math.max(maxDigits, Math.floor(Math.log10(num) + 1));
}
return maxDigits;
}
// Hàm lấy chữ số ở vị trí cụ thể trong một số
function getDigit(num: number, place: number): number {
return Math.floor(num / Math.pow(10, place)) % 10;
}
Deno.test('standard array', () => {
const input = [121, 432, 564, 23, 1, 45, 788];
const output = input.toSorted((a, b) => a - b);
expect(radixSort(input)).toStrictEqual(output);
});
Big O
Trong trường hợp tốt nhất, độ phức tạp thời gian của Sắp Xếp Theo Cơ Số là O(n⋅k), ta có thể đơn giản hóa thành O(n). Điều này xảy ra khi có rất nhiều giá trị cần sắp xếp, nhưng mỗi giá trị có ít chữ số. Ví dụ, với một triệu số mà mỗi số có ba chữ số, như số lớn nhất là 999, thì Sắp Xếp Theo Cơ Số rất hiệu quả.
Trong trường hợp xấu nhất, độ phức tạp thời gian của Sắp Xếp Theo Cơ Số có thể lên đến O(n^2). Điều này có thể xảy ra khi số chữ số của giá trị lớn nhất gần bằng số lượng các giá trị. Dù không phổ biến, nhưng đây là một tình huống mà Sắp Xếp Theo Cơ Số không tối ưu.
Trong trường hợp trung bình, độ phức tạp thời gian của Sắp Xếp Theo Cơ Số là O(n log n). Điều này thường xảy ra khi số chữ số của giá trị lớn nhất là k(n) = log n, ví dụ như khi chúng ta có một triệu số, mỗi số có khoảng 6 chữ số.
Độ phức tạp không gian của Radix Sort là O(n + k), bởi vì nó cần thêm bộ nhớ cho các bucket và các mảng tạm thời trong quá trình sắp xếp.
Toàn Cảnh
Sắp Xếp Theo Cơ Số là một phần của nhóm thuật toán sắp xếp theo thứ tự chữ số, không dựa trên so sánh. So với các thuật toán sắp xếp khác như Sắp Xếp Nhanh hay Sắp Xếp Trộn, Sắp Xếp Theo Cơ Số có sự khác biệt rõ ràng vì nó tập trung vào cách phân loại từng chữ số.
Trong các hệ thống mà các phần tử đều có dạng số nguyên và không có quá nhiều chữ số, Sắp Xếp Theo Cơ Số là lựa chọn tối ưu. Thêm vào đó, trong các hệ thống mà bộ nhớ có hạn và không có nhu cầu so sánh từng phần tử, Sắp Xếp Theo Cơ Số trở thành lựa chọn lý tưởng.
Khi kết hợp với Sắp Xếp Phân Phối ở từng bước xử lý chữ số, Sắp Xếp Theo Cơ Số thậm chí có thể cải thiện hiệu suất, giúp sắp xếp nhanh hơn nhiều trong các trường hợp cụ thể.
Điều đáng chú ý là Sắp Xếp Theo Cơ Số không phù hợp cho các dãy có phần tử dạng chuỗi không đồng đều về độ dài, vì việc sắp xếp sẽ trở nên phức tạp.
Ứng Dụng
Sắp Xếp Theo Cơ Số thường được ứng dụng trong các hệ thống xử lý dữ liệu lớn, nơi cần sắp xếp nhanh chóng một lượng lớn các giá trị số có cùng độ dài chữ số. Ví dụ, trong các hệ thống ngân hàng hoặc bảo hiểm, các mã số khách hàng có độ dài đồng đều và có thể được sắp xếp nhanh chóng bằng Sắp Xếp Theo Cơ Số.
Trong khoa học máy tính, Sắp Xếp Theo Cơ Số là công cụ hữu ích để xử lý các danh sách dữ liệu có cấu trúc đồng đều, ví dụ như số căn cước công dân hoặc mã số sinh viên.
Ngoài ra, Sắp Xếp Theo Cơ Số còn được sử dụng trong các bài toán xử lý số lớn trong các ngôn ngữ lập trình thấp như Assembly, nơi cần sắp xếp dữ liệu nhanh mà không tiêu tốn tài nguyên bộ nhớ.
Tuy nhiên, Sắp Xếp Theo Cơ Số không chỉ giới hạn ở số nguyên. Một số ứng dụng nâng cao còn mở rộng thuật toán để sắp xếp các dạng dữ liệu khác khi được mã hóa hợp lý.
Hiểu Lầm
Một hiểu lầm phổ biến là nghĩ rằng Sắp Xếp Theo Cơ Số luôn tốt hơn các thuật toán khác. Thực ra, Sắp Xếp Theo Cơ Số chỉ thật sự hiệu quả khi xử lý các số có cùng độ dài chữ số. Nếu không, các thuật toán so sánh truyền thống như Sắp Xếp Nhanh lại có thể hiệu quả hơn.
Nhiều người cũng cho rằng Sắp Xếp Theo Cơ Số hoạt động tốt với mọi loại dữ liệu. Nhưng thực tế, Sắp Xếp Theo Cơ Số không phù hợp để sắp xếp các dãy dữ liệu không đồng đều về kích thước hoặc không có dạng số.
Một giới hạn khác của Sắp Xếp Theo Cơ Số là việc tiêu tốn bộ nhớ do tạo ra các “xô” trong mỗi lần lặp. Điều này làm cho nó không phải là lựa chọn tốt khi bộ nhớ hệ thống hạn chế.
Cuối cùng, Sắp Xếp Theo Cơ Số có thể không linh hoạt khi so sánh với các thuật toán khác như Sắp Xếp Trộn, vì nó đòi hỏi các phần tử phải tuân theo một cấu trúc nhất định (số nguyên hoặc chuỗi có độ dài cố định).
Tóm Tắt
Sắp Xếp Theo Cơ Số là một thuật toán sắp xếp không so sánh, hoạt động bằng cách phân loại và xử lý từng chữ số của các số nguyên. Nó phù hợp cho các dãy số nguyên có độ dài chữ số đồng nhất.
Thuật toán này có độ phức tạp thời gian O(nk) trong mọi trường hợp, nhờ vào cách xử lý từng chữ số thay vì so sánh toàn bộ số. Tuy nhiên, nó đòi hỏi bộ nhớ phụ cho các “xô” chứa chữ số.
Sắp Xếp Theo Cơ Số có ứng dụng rộng rãi trong các hệ thống yêu cầu sắp xếp nhanh các dãy số đồng nhất về độ dài. Nhưng nó không phải là lựa chọn tối ưu cho mọi trường hợp sắp xếp, đặc biệt với các dãy không đồng đều.
Nhìn chung, Sắp Xếp Theo Cơ Số là công cụ mạnh mẽ khi được áp dụng đúng cách và với loại dữ liệu phù hợp, giúp tối ưu hiệu suất và bộ nhớ trong nhiều tình huống đặc thù.