Tổng quan
Counting Sort không so sánh hai phần tử nào. Nó xác định vị trí của mọi giá trị bằng cách đếm số lần xuất hiện của từng khóa, và đó là lý do nó thoát được cận dưới O(n log n) ràng buộc mọi thuật toán sắp xếp dựa trên so sánh.
Cái đánh đổi là nó chỉ áp dụng cho các khóa dùng làm chỉ số mảng được: số nguyên không âm nhỏ, hoặc thứ gì ánh xạ được về đó. Sắp xếp tuổi, điểm thi, ngày trong năm hay mức ưu tiên là chỗ nó tỏa sáng; sắp số thực bất kỳ hay chuỗi thì không phải việc của nó.
Counting Sort hoạt động thế nào?
- Tìm khoảng giá trị của khóa và cấp phát một mảng đếm kích thước k, với k là số khóa khả dĩ phân biệt.
- Duyệt đầu vào một lượt, tăng count[khóa] cho mỗi phần tử.
- Biến các số đếm thành tổng tích lũy: mỗi ô trở thành số phần tử nhỏ hơn hoặc bằng khóa đó, cũng chính là vị trí kết thúc của nó trong kết quả.
- Duyệt đầu vào theo chiều ngược, đặt mỗi phần tử vào output[count[khóa] − 1] rồi giảm số đếm đó đi một.
- Chép kết quả trở lại nếu cần sắp ngay trên mảng gốc.
Khi nào nên dùng?
- Sắp số nguyên có khoảng giá trị biết trước và vừa phải — tuổi, điểm trên thang 100, xếp hạng, mã trạng thái HTTP.
- Làm lượt bên trong của radix sort, nơi tính ổn định của nó là thứ khiến thuật toán bên ngoài đúng.
- Dựng biểu đồ tần suất và thứ tự đã sắp trong cùng một lượt, vì mảng đếm chính là biểu đồ tần suất.
- Không hợp khi k lớn so với n — sắp một nghìn giá trị rải trên một tỉ khóa khả dĩ sẽ cấp phát một tỉ thùng.
Phân tích độ phức tạp
Thời gian là O(n + k) trong mọi trường hợp: một lượt qua n phần tử và một lượt qua k thùng, không có rẽ nhánh phụ thuộc dữ liệu. Bộ nhớ là O(k) cho mảng đếm cộng O(n) cho kết quả. Toàn bộ phương pháp phụ thuộc vào việc k giữ ở mức tương đương n — khi k lớn hơn nhiều, cả bộ nhớ lẫn lượt quét thùng đều chiếm ưu thế, và một thuật toán so sánh sẽ thắng bất chấp thừa số log.
Câu hỏi thường gặp
Vì sao bước cuối lại duyệt đầu vào theo chiều ngược?
Đó là thứ khiến thuật toán ổn định. Đi ngược sẽ đặt lần xuất hiện cuối cùng của một khóa vào vị trí cao nhất mà nó sở hữu, nên các bản ghi vốn đã đúng thứ tự tương đối vẫn giữ nguyên. Đi xuôi thì các khóa bằng nhau ra theo thứ tự ngược lại.
Nó có xử lý được số âm không?
Có, bằng cách dịch chuyển. Trừ mọi khóa đi min để giá trị nhỏ nhất thành chỉ số 0, rồi cộng lại khi đọc ra. Kích thước mảng đếm trở thành max − min + 1.
Nó có phá vỡ cận dưới O(n log n) của sắp xếp không?
Nó đi vòng chứ không phá. Cận đó chỉ áp dụng cho các thuật toán mà thao tác duy nhất trên khóa là so sánh. Counting sort dùng khóa làm địa chỉ, đó là thông tin thêm mà một thuật toán so sánh không được phép giả định là mình có.