Counting Sort

Chào các bạn!

Tiếp theo chuỗi series về các thuật toán sắp xếp và tìm kiếm căn bản, thì ở bài viết này mình sẽ trình bày các bạn phần thuật toán Sắp xếp đếm - Counting Sort.

Đây là một thuật toán sắp xếp có lẽ đặc biệt khác so với các thuật toán trước đó. Nó không phụ thuộc vào số lượng phần tử của dãy số, mà lại phụ thuộc vào giá trị mà dãy số này chứa.

Hãy cùng tìm hiểu nó ngay sau đây nhé!

Đặt vấn đề

Cho dãy số gồm $N$ phần tử, việc của bạn là sắp xếp chúng theo thứ tự tăng dần. Tất nhiên $N$ ứng với cả triệu số.

Kèm các điều kiện đặc biệt:

• Các phần tử đều là số nguyên không âm, có giá trị không quá $1.000.000$

Ý tưởng thuật toán

Thay vì ta xử lý so sánh và đổi chỗ như những thuật toán trước đây, thì ta dùng một hàm map để đếm số lần giá trị này xuất hiện trong dãy số.

Hàm mapping được định nghĩa như sau:

$f(X) = k$

Ở đây:

1. $X$ là một giá trị bất kì nằm trong dãy số,
2. $k$ là số lần xuất hiện của giá trị $X$ trong dãy số

Để ý ra rằng, hàm $f(X)$ này chính là $count(X)$. Và quay lại điều kiện nêu ra ở khúc đặt vấn đề, ta thấy các giá trị của dãy số chỉ nằm trong đoạn $[0; 1.000.000]$. Do đó, ta có thể xây dựng thuật toán này như sau:

1. Khởi tạo: Khởi tạo một mảng counting có 1.000.000 + 1 phần tử
2. Reset: Set tất cả các giá trị từ vị trí 0 đến 1.000.000 bằng 0
3. Đếm: Lướt qua từng phần tử của dãy số đã cho ban đầu, thực hiện: counting[arr[i]]++
4. Điền: Chạy qua các giá trị từ vị trí 0 đến 1.000.000 của counting, ta điền đúng số lượng số lượng số đó vào dãy số ban đầu.

Tới đây, bạn đã hiểu vì sao thuật toán này được gọi là thuật toán sắp xếp đếm chưa nào. Đó là vì nó đếm luôn giá trị nằm trong dãy số đã cho luôn, rồi sau đó cứ thế điền lại vào thôi.

Tuy bạn cần chú ý đặc thù của thuật toán này, mà điều kiện giá trị của phần tử trong dãy là yếu tố quyết định.

Và dưới đây là code mà mình đã chuẩn bị:

void countingSort(int *arr, int l, int r) {
    // Reset
    for (int value=0; value<=maxNumber; value++) counting[value] = 0;
    
    // Đếm
    for (int i=l; i<=r; i++) counting[arr[i]]++;

    // Điền vào
    for (int value=0; value<=maxNumber; value++) {
        while (counting[value]) {
            arr[l++] = value;
            counting[value]--;
        }
    }
}

Full code bạn có thể xem ở đây: https://ideone.com/qmLz6H

Đánh giá độ phức tạp

Dễ thấy rằng, độ phức tạp của giải thuật trên là $O(N + maxValue)$ bất kể dãy số ban đầu có thứ tự như thế nào và dù có số lượng bao nhiêu đi nữa.

Và nếu bạn nhấn vào link full code ở phía trên, không bất ngờ bạn cũng có thể tìm thấy dòng Memory + thời gian thực thi:

Success #stdin #stdout 0.02s 7456KB

Với thời gian thực thi nhanh hơn hẳn các thuật toán trước đó mình trình bày với dãy số 1 triệu phần tử.

Kết luận

Trên đây, mình đã trình bày các bạn về thuật toán Counting Sort. Hi vọng bài viết sẽ giúp bạn phần nào hiểu được ý tưởng cũng như cài đặt nó mà không cần học thuộc bất cứ dòng code nào.

Nếu bạn có bất cứ ý kiến nào đóng góp, xin hãy gửi comment, mình sẽ trả lời và khắc phục cho những lần sau.