Bỏ qua đến nội dung chính
Mục lục

Sắp xếp đếm (counting sort) trong Python

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 19/20 · Chương 23

Cấu trúc dữ liệu và giải thuật

  • 8 phút
  • Trung cấp
  • Python 3.14
  • Cập nhật

Sắp xếp đếm (counting sort) là thuật toán sắp xếp không so sánh hai phần tử với nhau mà đếm xem mỗi giá trị xuất hiện bao nhiêu lần. Bạn dùng nó với số nguyên trong khoảng nhỏ, ví dụ xếp khách theo số quầy từ 1 đến 5, khi đó nó chỉ cần O(n + k) bước với k là độ rộng của khoảng.

Cần biết trước: mẫu đếm tần suất, nối list bằng extend() và tổng quan thuật toán sắp xếp.

Đếm số lần xuất hiện của từng giá trị

Mỗi khách được gọi tới một quầy, số quầy từ 1 đến 5. Thay cho dict của mẫu đếm tần suất, counting sort dùng một list có một ô cho mỗi giá trị: ô dem[q] giữ số khách ở quầy q. List [0] * (max(quay) + 1) có đủ ô từ 0 tới số quầy lớn nhất:

python
quay = [3, 1, 4, 1, 5, 3, 1]
dem = [0] * (max(quay) + 1)
for q in quay:
    dem[q] += 1
print(dem)

KẾT QUẢ

[0, 3, 0, 2, 1, 1]

Ô 0 bằng 0 vì không có quầy số 0. Ô 1 bằng 3 vì ba khách vào quầy 1. Vòng lặp đi qua dữ liệu một lần và không có phép so nào giữa hai khách: chỉ số của list làm việc mà phép so làm trong các thuật toán trước.

Dựng lại list đã xếp từ bảng đếm

Đọc bảng đếm từ ô 0 lên ô cuối, mỗi giá trị được viết lại đúng số lần đã đếm. Toán tử * lặp list [gia_tri] và extend() nối kết quả vào cuối:

python
quay = [3, 1, 4, 1, 5, 3, 1]
dem = [0] * (max(quay) + 1)
for q in quay:
    dem[q] += 1

da_xep = []
for gia_tri in range(len(dem)):
    da_xep.extend([gia_tri] * dem[gia_tri])
print(da_xep)

KẾT QUẢ

[1, 1, 1, 3, 3, 4, 5]

Vòng đếm tốn n bước, vòng dựng lại đi qua k ô và viết tổng cộng n phần tử. Tổng cộng là O(n + k). Theo bài Big O, khi k nhỏ so với n thì nó thường nhanh hơn các thuật toán phải so sánh phần tử, vì những thuật toán đó cần ít nhất cỡ n log n phép so trong trường hợp xấu nhất.

Khoảng giá trị quyết định tất cả

Số âm làm chỉ số của list đếm sai lệch. Danh sách dưới đây là chênh lệch số khách của từng quầy so với hôm qua, có cả số âm. Lời giải là dời mọi giá trị theo số nhỏ nhất, để số nhỏ nhất rơi vào ô 0:

python
chenh = [2, -1, 0, 3, -1]
nho_nhat = min(chenh)
dem = [0] * (max(chenh) - nho_nhat + 1)
for x in chenh:
    dem[x - nho_nhat] += 1

da_xep = []
for k in range(len(dem)):
    da_xep.extend([k + nho_nhat] * dem[k])
print(dem)
print(da_xep)

KẾT QUẢ

[2, 1, 0, 1, 1]
[-1, -1, 0, 2, 3]

Ô dem[0] giữ số lần của -1, ô dem[4] giữ số lần của 3. Đổi - nho_nhat + 1 thành - nho_nhat + 3 rồi chạy lại: dòng đầu in [2, 1, 0, 1, 1, 0, 0], hai ô thừa ở cuối vẫn bằng 0 và kết quả không đổi. Số ô chỉ phụ thuộc khoảng giá trị, không phụ thuộc số phần tử:

python
so_ve = [1000000, 7, 12]
so_o = max(so_ve) - min(so_ve) + 1
print(so_o, "ô đếm cho", len(so_ve), "số")

KẾT QUẢ

999994 ô đếm cho 3 số

Ba số vé cần gần một triệu ô đếm, và vòng dựng lại phải đi qua từng ô. Vì vậy counting sort chỉ hợp với số nguyên trong khoảng nhỏ: điểm thi từ 0 đến 10, số quầy, tuổi. Số thực hay chuỗi không làm chỉ số của list được. Bài radix sort dùng counting sort nhiều lần, mỗi lần theo một chữ số, để xếp được số lớn.

Xếp bản ghi và giữ thứ tự cũ

Cách dựng lại ở trên chỉ viết lại con số, nên mất tên khách đi kèm. Để xếp bản ghi (ten, quay), bạn tính vị trí đầu của mỗi quầy trong list kết quả: vị trí đầu của quầy q bằng vị trí đầu của quầy trước cộng số khách của quầy trước. Sau đó đi qua khách theo thứ tự cũ, đặt mỗi người vào vị trí của quầy mình rồi tăng vị trí đó lên một:

python
khach = [("An", 3), ("Bình", 1), ("Chi", 3), ("Dũng", 2), ("Hà", 1)]
dem = [0] * 4
for ten, quay in khach:
    dem[quay] += 1
vi_tri = [0] * 4
for q in range(1, 4):
    vi_tri[q] = vi_tri[q - 1] + dem[q - 1]
print("Vị trí đầu:", vi_tri)
ket_qua = [None] * len(khach)
for ten, quay in khach:
    ket_qua[vi_tri[quay]] = (ten, quay)
    vi_tri[quay] += 1
print(ket_qua)

KẾT QUẢ

Vị trí đầu: [0, 0, 2, 3]
[('Bình', 1), ('Hà', 1), ('Dũng', 2), ('An', 3), ('Chi', 3)]

Hai khách quầy 1 là Bình và Hà chiếm vị trí 0 và 1 theo đúng thứ tự họ xuất hiện. Tương tự An vẫn đứng trước Chi. Vì vậy cách đặt theo vị trí đầu là ổn định, và đó là tính chất mà radix sort cần. Vòng cuối sửa trực tiếp list vi_tri, nên muốn giữ các vị trí đầu thì phải đặt khách bằng một bản sao.

Kiểm tra nhanh

  1. Đếm [2, 0, 2, 4] vào dem = [0] * (max(ds) + 1) như bài. dem là gì?

    • [1, 2, 1]
    • [1, 0, 2, 0, 1]
    • [1, 0, 2, 1]
  2. Những điều nào đúng với counting sort?

    • Nó so sánh từng cặp phần tử như sắp xếp nổi bọt
    • Số ô của list đếm phụ thuộc khoảng giá trị, không phụ thuộc số phần tử
    • Đặt bản ghi theo vị trí đầu và duyệt theo thứ tự cũ thì giữ được thứ tự của các bản ghi bằng nhau
    • Nó xếp được list chuỗi tên khách bằng cách dùng tên làm chỉ số
  3. Tạo dem = [0] * max(quay) rồi đếm quay = [2, 1, 2]. Chuyện gì xảy ra?

    • dem là [0, 1, 2]
    • Báo lỗi IndexError
    • dem là [1, 2]
  4. Đếm [1, -1] vào dem = [0] * (max(ds) + 1) mà không dời theo số nhỏ nhất, rồi dựng lại như bài. Kết quả là gì?

    • [-1, 1]
    • [1]
    • [1, 1]
Đúng hết lần đầu +15 XP

Bài tập

Xếp khách theo quầy bằng counting sort

Mỗi khách là một tuple (ten, quay) với quay từ 1 đến so_quay. Viết thân hàm xep_theo_quay(khach, so_quay) xếp khách theo quầy bằng counting sort. List dem có so_quay + 1 ô, ô q là số khách ở quầy q. List vi_tri_dau cũng có so_quay + 1 ô, ô q là vị trí đầu của quầy q trong kết quả. Đặt từng khách vào chỗ theo thứ tự trong khach, nên khách cùng quầy giữ thứ tự cũ. Không dùng phép so nào (<, <=, >, >=, ==, !=), không dùng min(), tham số key, sorted() hay sort(), và không sửa khach.

Ví dụ: xep_theo_quay([("An", 3), ("Bình", 1), ("Chi", 3), ("Dũng", 2), ("Hà", 1)], 4) trả về ([0, 2, 1, 2, 0], [0, 0, 2, 3, 5], [("Bình", 1), ("Hà", 1), ("Dũng", 2), ("An", 3), ("Chi", 3)]).

Trả về: dem, vi_tri_dau và list khách đã xếp, một tuple.

python
def xep_theo_quay(khach, so_quay):
    pass  # Viết thân hàm thay cho dòng này

Tóm tắt

  • Counting sort không so sánh phần tử: nó đếm số lần xuất hiện vào list có một ô cho mỗi giá trị.

  • List đếm cần max + 1 ô, thiếu một ô thì báo IndexError.

  • Có số âm thì dời theo số nhỏ nhất, nếu không chỉ số âm âm thầm cộng vào ô cuối.

  • Thời gian là O(n + k) và bộ nhớ là O(k), nên nó chỉ hợp với số nguyên trong khoảng nhỏ.

  • Tính vị trí đầu của mỗi giá trị rồi đặt bản ghi theo thứ tự cũ cho một cách xếp ổn định.

Câu hỏi thường gặp

Sắp xếp đếm (counting sort) là gì và khi nào nên dùng?

Đó là cách xếp bằng đếm: dùng giá trị làm chỉ số của list đếm, rồi viết lại theo bảng đếm. Nên dùng khi dữ liệu là số nguyên trong khoảng nhỏ so với số phần tử, ví dụ điểm thi hay số quầy của hàng nghìn khách.

Có thể đếm bằng dict thay cho list không?

Có. Mẫu d[x] = d.get(x, 0) + 1 của bài đếm tần suất đếm được cả khi khoảng giá trị lớn nhưng thưa. Khi dựng lại, bạn vẫn phải đi từ số nhỏ nhất tới số lớn nhất và hỏi d.get(x, 0) cho từng số. Python còn có collections.Counter cho việc đếm, xem bài Counter.

Vì sao counting sort không xếp được số thực hay chuỗi?

Vì nó dùng chính giá trị làm chỉ số của list, mà chỉ số phải là số nguyên. Với số thực hay chuỗi, hãy dùng sorted(), theo bài tổng quan thuật toán sắp xếp.

Sắp xếp đếm có nhanh hơn hàm sorted() của Python không?

Có thể, khi khoảng giá trị nhỏ và list rất dài. Nhưng hàm tự viết bằng Python chạy từng lệnh một, còn sorted() viết bằng C, nên với list ngắn hay khoảng giá trị rộng thì sorted() thường nhanh hơn. Hãy đo bằng dữ liệu của bạn trước khi chọn.

Chủ đề

counting sort

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE

  • Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
  • Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
  • Xây hệ thống AI cho doanh nghiệp tại VietPlatform.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập