Sắp xếp đếm (counting sort) trong Python
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
Trong bài này · 12
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:
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:
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:
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ử:
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:
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
Đếm
[2, 0, 2, 4]vàodem = [0] * (max(ds) + 1)như bài.demlà gì?[1, 2, 1][1, 0, 2, 0, 1][1, 0, 2, 1]
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ố
Tạo
dem = [0] * max(quay)rồi đếmquay = [2, 1, 2]. Chuyện gì xảy ra?demlà[0, 1, 2]- Báo lỗi IndexError
demlà[1, 2]
Đếm
[1, -1]vàodem = [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]
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.
def xep_theo_quay(khach, so_quay):
pass # Viết thân hàm thay cho dòng nàyTó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áoIndexError.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ủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
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.