Sắp xếp theo cơ số
Sắp xếp theo cơ số là thuật toán khác biệt nhất trong các thuật toán sắp xếp: nó không bao giờ hỏi giá trị nào trong hai giá trị lớn hơn. Nó đọc các số theo từng chữ số và sắp xếp chúng mỗi lần theo một chữ số, dùng mười thùng. Ý tưởng này còn lâu đời hơn máy tính: các máy phân loại thẻ đục lỗ đã hoạt động như vậy.
Ý tưởng
Sắp xếp các số chỉ theo chữ số hàng đơn vị. Sau đó sắp xếp theo chữ số hàng chục, nhưng theo cách giữ các số có cùng chữ số hàng chục theo thứ tự mà lượt đầu đã tạo ra. Rồi theo hàng trăm, cũng theo cách đó. Sau lượt cuối, danh sách đã được sắp xếp: hàng trăm quyết định trước, các số cùng hàng trăm đã theo thứ tự hàng chục, và các số cùng cả hàng chục đã theo thứ tự hàng đơn vị.
Một lượt, với các thùng
Mỗi lượt dùng mười thùng, mỗi thùng cho một chữ số từ 0 đến 9. Duyệt danh sách từ đầu đến cuối và chuyển mỗi số vào thùng của chữ số đó, xếp sau các số đã có ở đó. Sau đó đổ các thùng trở lại danh sách theo thứ tự, thùng 0 trước. Chuyển các số theo thứ tự danh sách và thêm vào cuối thùng chính là điều giữ cho lượt đó ổn định. Ứng dụng đếm số lượng số cho mỗi chữ số trước, nên các thùng có thể nằm cạnh nhau trên một hàng, mỗi thùng bắt đầu ngay sau thùng trước: đó là sắp xếp đếm trên một chữ số.
Một ví dụ
Lấy 170, 45, 75, 90, 802, 24, 2, 66. Theo chữ số hàng đơn vị: 170, 90, 802, 2, 24, 45, 75, 66. Theo chữ số hàng chục: 802, 2, 24, 45, 66, 170, 75, 90; lưu ý rằng 802 và 2, cả hai đều có chữ số hàng chục là 0, giữ thứ tự từ lượt đầu. Theo chữ số hàng trăm: 2, 24, 45, 66, 75, 90, 170, 802. Ba lượt qua tám số: đọc 24 chữ số và 48 lần di chuyển, không một phép so sánh nào.
Nhanh đến mức nào?
Mỗi lượt đọc một chữ số của mọi số và di chuyển mọi số hai lần, nên với n số có d chữ số, khối lượng công việc tăng theo n · d. Sắp xếp so sánh cần ít nhất khoảng n log₂ n phép so sánh trong trường hợp xấu nhất, vì nó phải phân biệt n! thứ tự có thể bằng từng câu hỏi có-hay-không một. Sắp xếp theo cơ số không bị giới hạn đó, vì nó không bao giờ đặt những câu hỏi như vậy. Với nhiều khóa ngắn, như một triệu số dưới 1.000, ba lượt ít việc hơn nhiều so với khoảng 20 triệu phép so sánh mà sắp xếp so sánh cần. Với khóa dài hoặc ít giá trị, lợi thế này biến mất.
LSD và MSD, cùng lịch sử
Phiên bản ở đây bắt đầu từ chữ số có nghĩa nhỏ nhất (LSD). Cách ngược lại, chữ số có nghĩa lớn nhất trước (MSD), chia danh sách vào các thùng theo chữ số đầu tiên và sắp xếp riêng từng thùng, phù hợp với các chuỗi có độ dài khác nhau. Sắp xếp theo cơ số bắt nguồn từ các máy phân loại thẻ đục lỗ ra đời sau các máy lập bảng của Herman Hollerith dùng cho cuộc điều tra dân số Hoa Kỳ năm 1890: máy phân loại thả mỗi thẻ vào một trong mười ngăn theo lỗ đục ở một cột, và người vận hành cho cả xấp thẻ chạy qua một lần cho mỗi cột, bắt đầu từ cột cuối.
Khám phá
Mở ứng dụng và nhấn Bước. Mỗi lượt trước tiên đếm các chữ số, từ đó vạch ra các thùng 0 đến 9 ở hàng dưới danh sách. Sau đó các số lần lượt rơi vào thùng của mình, thùng đang dùng được tô sáng, rồi được chép trở lại. Tự nhập các số đến 999, chẳng hạn ví dụ ở trên, để xem cả ba lượt.
Câu hỏi thường gặp
Độ phức tạp thời gian của sắp xếp theo cơ số là gì?
O(n · d) với n khóa có d chữ số trong một cơ số cố định, cộng thêm chi phí các thùng cho mỗi lượt. Nó cần thêm O(n) bộ nhớ cho vùng đệm chứa các thùng.
Sắp xếp theo cơ số có ổn định không?
Sắp xếp theo cơ số LSD bắt buộc phải ổn định: nó chỉ đúng vì mỗi lượt giữ các giá trị có cùng chữ số theo thứ tự chúng đi vào. Do đó kết quả cuối cùng cũng ổn định.
Sắp xếp theo cơ số có xử lý được số âm hay số thập phân không?
Không trực tiếp, nhưng có thể nhờ một mẹo: dịch các số âm để tất cả đều dương, hoặc sắp xếp riêng chúng rồi đảo ngược. Số dấu phẩy động có thể được sắp xếp theo mẫu bit sau một phép biến đổi nhỏ.
Vì sao dùng cơ số 10?
Vì dễ theo dõi. Máy tính thường sắp xếp mỗi lần 8 hoặc 16 bit, nên một số 32 bit cần bốn hoặc hai lượt, với 256 hoặc 65.536 thùng.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Thử sắp xếp theo cơ số