Sắp xếp đếm

Sắp xếp đếm sắp xếp các phần tử bằng cách đếm số lần xuất hiện của chúng và thường được áp dụng cho các mảng số nguyên.

Triển khai đơn giản

Hãy bắt đầu với một ví dụ đơn giản. Cho một mảng nums có độ dài \(n\), trong đó tất cả phần tử đều là "số nguyên không âm", quy trình tổng thể của sắp xếp đếm được thể hiện trong hình dưới đây.

1. Duyệt qua mảng để tìm số lớn nhất, ký hiệu là \(m\), sau đó tạo một mảng phụ trợ counter có độ dài \(m + 1\).
2. Sử dụng counter để đếm số lần xuất hiện của mỗi số trong nums, trong đó counter[num] lưu trữ số lần xuất hiện của num. Thao tác này rất đơn giản: duyệt qua nums (ký hiệu số hiện tại là num) và tăng counter[num] thêm \(1\) sau mỗi lần gặp.
3. Vì các chỉ số của counter được sắp xếp theo thứ tự tự nhiên, các số này thực chất đã được sắp xếp. Tiếp theo, duyệt qua counter và ghi các số trở lại nums theo thứ tự tăng dần dựa trên số lần xuất hiện của chúng.

Mã nguồn ví dụ được hiển thị dưới đây:

[file]{counting_sort}-[class]{}-[func]{counting_sort_naive}

Mối liên hệ giữa sắp xếp đếm và sắp xếp theo xô

Dưới góc nhìn của sắp xếp theo xô (bucket sort), mỗi chỉ số của mảng đếm counter có thể được coi là một chiếc xô (bucket), và quá trình đếm có thể được xem là việc phân chia các phần tử vào các xô tương ứng của chúng. Về bản chất, sắp xếp đếm là một trường hợp đặc biệt của sắp xếp theo xô đối với dữ liệu số nguyên.

Triển khai hoàn chỉnh

Người đọc tinh ý có thể đã nhận ra rằng nếu dữ liệu đầu vào bao gồm các đối tượng (object), bước 3. ở trên sẽ không còn hoạt động. Giả sử dữ liệu đầu vào là các đối tượng sản phẩm và chúng ta muốn sắp xếp chúng theo giá cả (một biến thành viên của lớp); thuật toán trên sẽ chỉ tạo ra thứ tự đã sắp xếp của riêng các mức giá.

Vậy làm thế nào để chúng ta có được thứ tự sắp xếp của dữ liệu gốc? Đầu tiên, chúng ta tính tổng tiền tố (prefix sum) của counter. Đúng như tên gọi, tổng tiền tố tại chỉ số i, ký hiệu là prefix[i], bằng tổng các phần tử từ chỉ số 0 đến i:

\[ \text{prefix}[i] = \sum_{j=0}^i \text{counter[j]} \]

Tổng tiền tố có một ý nghĩa biểu thị rõ ràng: prefix[num] - 1 chính là chỉ số của lần xuất hiện cuối cùng của phần tử num trong mảng kết quả res. Thông tin này vô cùng quan trọng vì nó cho biết vị trí mà mỗi phần tử cần được đặt vào trong mảng kết quả. Tiếp theo, chúng ta duyệt ngược mảng gốc nums (từ phải qua trái), và đối với mỗi phần tử num, thực hiện hai bước sau.

1. Đặt num vào chỉ số prefix[num] - 1 của mảng res.
2. Giảm tổng tiền tố prefix[num] đi \(1\) để có được chỉ số cho lần đặt tiếp theo của num.

Sau khi quá trình duyệt hoàn tất, mảng res sẽ chứa kết quả đã được sắp xếp, và cuối cùng res được sử dụng để ghi đè lên mảng gốc nums. Quy trình sắp xếp đếm hoàn chỉnh được thể hiện trong hình dưới đây.

<1><2><3><4><5><6><7><8>

Triển khai thuật toán sắp xếp đếm được hiển thị dưới đây:

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

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

• Độ phức tạp thời gian là \(O(n + m)\), không mang tính thích ứng: Duyệt qua nums và counter đều mất thời gian tuyến tính. Nói chung, khi \(n \gg m\), độ phức tạp thời gian sẽ tiệm cận \(O(n)\).
• Độ phức tạp không gian là \(O(n + m)\), sắp xếp không tại chỗ: Sử dụng các mảng res và counter lần lượt có độ dài là \(n\) và \(m\).
• Sắp xếp ổn định: Vì các phần tử được điền vào res theo thứ tự từ "phải qua trái", việc duyệt ngược mảng nums có thể tránh làm thay đổi vị trí tương đối của các phần tử bằng nhau, từ đó đạt được sắp xếp ổn định. Trên thực tế, duyệt mảng nums theo chiều thuận cũng có thể cho ra kết quả sắp xếp đúng, nhưng kết quả đó sẽ không ổn định.

Hạn chế

Đến đây, bạn có thể nghĩ rằng sắp xếp đếm khá khéo léo vì nó đạt được hiệu quả sắp xếp chỉ bằng cách đếm số lần xuất hiện. Tuy nhiên, các điều kiện tiên quyết để sử dụng sắp xếp đếm là khá khắt khe.

Sắp xếp đếm chỉ áp dụng cho các số nguyên không âm. Để áp dụng nó cho các loại dữ liệu khác, bạn phải đảm bảo rằng chúng có thể được chuyển đổi thành số nguyên không âm mà không làm thay đổi thứ tự tương đối của các phần tử. Ví dụ, đối với một mảng số nguyên có chứa số âm, trước tiên bạn có thể cộng thêm một hằng số vào mỗi số để chuyển chúng sang phạm vi không âm, sau đó dịch chuyển ngược lại sau khi đã sắp xếp.

Sắp xếp đếm rất phù hợp với các trường hợp có số lượng phần tử lớn nhưng phạm vi giá trị nhỏ. Ví dụ, trong trường hợp trên, \(m\) không thể quá lớn; nếu không, nó sẽ tiêu tốn quá nhiều không gian bộ nhớ. Và khi \(n \ll m\), sắp xếp đếm mất thời gian \(O(m)\), việc này có thể chậm hơn so với các thuật toán sắp xếp có độ phức tạp thời gian là \(O(n \log n)\).