Thuật toán sắp xếp đếm: cách hoạt động, mã và độ phức tạp

Sắp xếp đếm giải quyết vấn đề gì

Mọi thuật toán chỉ so sánh từng cặp phần tử đều cần Ω(n log n) phép so sánh ở trường hợp xấu nhất. Sắp xếp đếm tránh giới hạn này bằng cách không so sánh gì cả: nó dùng chính khóa làm chỉ số mảng. Khi các khóa là số nguyên nhỏ, như điểm thi từ 0 đến 100, tuổi, byte từ 0 đến 255 hay số sao đánh giá, cách này nhanh hơn mọi thuật toán sắp xếp dựa trên so sánh.

Cái giá phải trả là bộ nhớ tỉ lệ với khoảng giá trị của khóa. Sắp xếp một ít số nguyên 64 bit rải khắp miền giá trị sẽ cần mảng đếm lớn đến mức không thể.

Ý tưởng và ví dụ minh họa

Sắp xếp [4, 2, 2, 8, 3, 3, 1], có các giá trị nằm trong khoảng 0 đến 8 (k = 9).

1. Đếm từng giá trị: count[v] là số lần v xuất hiện.
2. Tổng tiền tố: thay mỗi số đếm bằng số phần tử nhỏ hơn hoặc bằng giá trị đó. Khi đó count[v] là vị trí ngay sau vị trí cuối cùng nơi v thuộc về.
3. Đặt phần tử: duyệt đầu vào từ phải sang trái; với mỗi giá trị v, giảm count[v] và ghi v vào vị trí đó. Duyệt từ phải sang trái giữ nguyên thứ tự ban đầu của các giá trị bằng nhau.

Vậy số 1 đi vào chỉ số 0, hai số 2 vào chỉ số 1 và 2, hai số 3 vào 3 và 4, số 4 vào chỉ số 5 và số 8 vào chỉ số 6. Kết quả: [1, 2, 2, 3, 3, 4, 8].

Cài đặt bằng Python

Phiên bản ổn định này sắp xếp các đối tượng bất kỳ theo khóa số nguyên từ 0 đến k - 1.

def counting_sort(items, k, key=lambda x: x):
    """Stable sort of items by integer key in range(k)."""
    count = [0] * k
    for x in items:
        count[key(x)] += 1
    for v in range(1, k):                # prefix sums
        count[v] += count[v - 1]
    out = [None] * len(items)
    for x in reversed(items):            # right to left: stable
        count[key(x)] -= 1
        out[count[key(x)]] = x
    return out

print(counting_sort([4, 2, 2, 8, 3, 3, 1], k=9))
# [1, 2, 2, 3, 3, 4, 8]
people = [("Ana", 3), ("Bo", 1), ("Cy", 3), ("Di", 2)]
print(counting_sort(people, k=4, key=lambda p: p[1]))
# [('Bo', 1), ('Di', 2), ('Ana', 3), ('Cy', 3)]

Khi chỉ sắp xếp các số nguyên thuần và không cần tính ổn định, có một phiên bản đơn giản hơn dựng lại đầu ra từ các số đếm. Biến thể này còn xử lý được số âm bằng cách dịch theo giá trị nhỏ nhất:

def counting_sort_ints(nums):
    if not nums:
        return []
    lo, hi = min(nums), max(nums)
    count = [0] * (hi - lo + 1)
    for x in nums:
        count[x - lo] += 1
    out = []
    for offset, c in enumerate(count):
        out.extend([offset + lo] * c)
    return out

print(counting_sort_ints([3, -1, 2, -1, 0]))   # [-1, -1, 0, 2, 3]

Độ phức tạp thời gian và không gian

Sắp xếp đếm là tuyến tính khi k là O(n). Nếu k lớn hơn n rất nhiều, ví dụ 1.000 giá trị trong khoảng 0 đến 10⁹, mảng đếm sẽ chiếm ưu thế và nên dùng sắp xếp dựa trên so sánh hoặc sắp xếp cơ số.

So sánh sắp xếp đếm với các thuật toán khác

Ở đây k là kích thước khoảng khóa, d là số chữ số và b là cơ số dùng trong sắp xếp cơ số. Sắp xếp đếm ổn định khi các phần tử được đặt bằng tổng tiền tố từ phải sang trái. Phiên bản dựng lại từ số đếm cho cùng kết quả với số nguyên thuần nhưng không mang theo được dữ liệu khác đi cùng khóa.

Biến thể và lỗi thường gặp

• Sắp xếp cơ số chạy một lần sắp xếp đếm ổn định cho mỗi chữ số, mở rộng ý tưởng sang số nguyên lớn và chuỗi độ dài cố định.
• Bucket sort rải giá trị vào các thùng theo khoảng và sắp xếp từng thùng; nó nhanh khi giá trị phân bố đều.
• Đếm mà không sắp xếp: thường bạn chỉ cần các số đếm, ví dụ để dựng biểu đồ tần suất hoặc tìm giá trị xuất hiện nhiều nhất. collections.Counter làm trực tiếp việc này.

Khi nào nên dùng sắp xếp đếm

Dùng khi khóa là số nguyên trong khoảng nhỏ so với số phần tử: điểm số, tuổi, ngày trong tháng, byte, giá trị kênh màu từ 0 đến 255, hoặc các giá trị enum nhỏ. Nó cũng là bước trong của sắp xếp cơ số và của các thuật toán dựng mảng hậu tố. Trong phỏng vấn, nó xuất hiện ở các câu như sort colors (giá trị 0, 1, 2), sắp xếp theo tần suất, H-index, và câu hỏi kinh điển làm sao vượt giới hạn O(n log n) của các thuật toán sắp xếp dựa trên so sánh.