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

Sắp xếp cơ số giải quyết vấn đề gì

Sắp xếp đếm là tuyến tính nhưng cần mảng đếm lớn bằng cả khoảng giá trị của khóa, điều không thể với số nguyên 32 bit hay 64 bit. Sắp xếp cơ số tách mỗi khóa thành các chữ số nhỏ và chạy sắp xếp đếm một lần cho mỗi chữ số, nên mỗi lượt chỉ cần mảng đếm b phần tử (10 cho chữ số thập phân, 256 cho byte).

Nó dùng được cho mọi khóa có thể tách thành một dãy cố định các ký hiệu nhỏ: số nguyên không âm, ngày viết dạng YYYYMMDD, mã có độ dài cố định như mã bưu chính, địa chỉ IP và chuỗi có độ rộng cố định.

Ví dụ minh họa: sắp xếp cơ số LSD trong cơ số 10

Sắp xếp [170, 45, 75, 90, 802, 24, 2, 66]. Số lớn nhất có 3 chữ số, nên có 3 lượt. Mỗi lượt là một lần sắp xếp ổn định theo một chữ số: các chữ số bằng nhau giữ thứ tự từ lượt trước.

Sau lượt 2, các số đã được sắp xếp theo hai chữ số cuối. Ở lượt 3, các số 2, 24, 45, 66, 75 và 90 đều có chữ số hàng trăm là 0, và tính ổn định giữ chúng theo thứ tự mà lượt 2 tạo ra. Đó là lý do mỗi lượt phải ổn định.

Cài đặt bằng Python

def counting_pass(nums, exp, base):
    """Stable counting sort of nums by the digit at exp."""
    count = [0] * base
    for x in nums:
        count[(x // exp) % base] += 1
    for d in range(1, base):
        count[d] += count[d - 1]
    out = [0] * len(nums)
    for x in reversed(nums):
        d = (x // exp) % base
        count[d] -= 1
        out[count[d]] = x
    return out

def radix_sort(nums, base=10):
    """LSD radix sort for non-negative integers."""
    if not nums:
        return []
    exp, biggest = 1, max(nums)
    while biggest // exp > 0:
        nums = counting_pass(nums, exp, base)
        exp *= base
    return nums

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]
print(radix_sort([3, 0, 1, 0], base=256))   # [0, 0, 1, 3]

Dùng cơ số 256 nghĩa là mỗi lượt xét một byte, nên số nguyên 32 bit chỉ cần 4 lượt. Để bao gồm số âm, hãy sắp xếp riêng các giá trị âm và không âm rồi ghép lại, hoặc dịch mọi khóa theo giá trị nhỏ nhất. Với chuỗi độ dài cố định, dùng mã ký tự ở vị trí i làm chữ số và đi từ vị trí cuối về vị trí đầu.

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

Khi d là hằng số (khóa có độ rộng cố định) và b được chọn gần n hoặc một giá trị cố định như 256, thời gian là O(n). Với n khóa đều khác nhau, d phải ít nhất là log_b n, nên sắp xếp cơ số không vượt O(n log n) với khóa kích thước tùy ý; nó nhanh vì mỗi bước là một thao tác mảng đơn giản.

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

Trong bảng, n là số khóa, k là khoảng khóa của sắp xếp đếm, d là số chữ số và b là cơ số. Sắp xếp cơ số LSD ổn định miễn là mỗi lượt chữ số đều ổn định. Nó cần khóa có cấu trúc cố định, trong khi các thuật toán dựa trên so sánh như sắp xếp trộn và sắp xếp nhanh làm việc với mọi thứ tự, kể cả hàm so sánh tùy chỉnh.

LSD so với MSD, và lỗi thường gặp

Khi nào nên dùng sắp xếp cơ số

Sắp xếp cơ số rất phù hợp với mảng lớn các số nguyên hoặc khóa có độ rộng cố định, như ID 32 bit, dấu thời gian, địa chỉ IPv4 hoặc chuỗi độ dài cố định, đặc biệt trên GPU và trong các thư viện hiệu năng cao nơi cách truy cập bộ nhớ đều đặn của nó phát huy tác dụng. Nó được dùng trong dựng mảng hậu tố và một số tải công việc cơ sở dữ liệu và đồ họa. Với list Python thông thường, sorted() gần như luôn nhanh hơn trong thực tế vì chạy bằng mã C đã tối ưu. Trong phỏng vấn, sắp xếp cơ số xuất hiện khi được hỏi cách sắp xếp trong thời gian tuyến tính, ví dụ bài Maximum Gap.