Chuyển tới nội dung chính

Sắp xếp phi so sánh (Counting · Radix · Bucket)

Bạn sẽ học được gì

Mọi thuật toán dựa trên so sánh đều bị chặn ở O(n log n) — đó là giới hạn lý thuyết không thể vượt. Nhưng nếu không so sánh mà dùng chính giá trị làm địa chỉ, ta có thể đạt O(n + k), tức tuyến tính. Bạn sẽ học ba thuật toán phi so sánh: Counting, Radix và Bucket sort.

1. Trực quan: đếm phiếu bầu thay vì so từng người​

Tưởng tượng bạn phải sắp 1000 lá phiếu, mỗi lá ghi một số từ 0 đến 9. Cách "so sánh" sẽ bắt bạn so từng cặp lá — chậm. Nhưng có cách thông minh hơn: chuẩn bị 10 cái rổ đánh số 0..9. Đọc từng lá, ném thẳng vào rổ tương ứng. Cuối cùng, đổ rổ 0, rồi rổ 1, ... ra — thế là đã sắp!

Bạn không hề so sánh hai lá phiếu nào với nhau. Bạn chỉ dùng giá trị của lá làm địa chỉ rổ. Đó là bí mật để vượt O(n log n).

phieu: [3 1 2 3 0 1 2 3]

dem so lan xuat hien:
  0:1   1:2   2:2   3:3

do ra theo thu tu:
  [0, 1, 1, 2, 2, 3, 3, 3]

2. Ba biến thể của một ý tưởng​

Thuật toánÝ tưởngĐộ phức tạpHợp khi
Countingđếm số lần mỗi khóa xuất hiện, rồi đổ raO(n + k)khóa nguyên, dải k nhỏ
Radixcounting theo từng chữ số, từ hàng đơn vị lênO(d(n + k))số/chuỗi độ dài d cố định
Bucketchia vào nhiều "xô" theo khoảng, sắp từng xôO(n) trung bìnhdữ liệu phân bố đều

k là độ rộng của dải giá trị (ví dụ 0..9 thì k = 10). Mấu chốt: nếu k không quá lớn so với n, ta được tuyến tính. Nhưng nếu k khổng lồ (ví dụ số tới một tỷ), counting sort tốn bộ nhớ O(k) khổng lồ — lúc đó nó không còn hợp lý.

3. Chạy debug: counting sort​

Xem ba pha của counting sort trên [3, 1, 2, 3, 0].

🐞 Counting sort [3, 1, 2, 3, 0]Bước 1/4
1a = [3, 1, 2, 3, 0]
2dem = [0, 0, 0, 0]      # k = 4 (gia tri 0..3)
3# pha 1: dem so lan xuat hien
4# dem = [1, 1, 1, 2]    (0:1, 1:1, 2:1, 3:2)
5# pha 2: do ra theo thu tu tang
6ket_qua = [0, 1, 2, 3, 3]
Biến tại bước này
a[3, 1, 2, 3, 0]
👉 Dải giá trị là 0..3 → cần mảng đếm 4 ô.

4. Code chạy được​

Đang tải trình chạy code…

5. Phân tích: nhanh nhưng kén dữ liệu​

  • Vì sao vượt được O(n log n)? Vì không so sánh phần tử với nhau. Giới hạn O(n log n) chỉ áp dụng cho thuật toán dựa trên so sánh. Counting dùng giá trị làm chỉ số → bỏ qua so sánh.
  • Điều kiện sống còn: khóa phải là số nguyên (hoặc ánh xạ được sang số nguyên) trong dải hẹp. Nếu k quá lớn, O(n + k) thoái hóa và tốn bộ nhớ O(k).
  • Radix sort vượt giới hạn k lớn của counting bằng cách xử lý từng chữ số một (mỗi chữ số chỉ có 10 giá trị). Phải dùng counting ổn định ở mỗi pha, nếu không kết quả sẽ sai.
  • Bucket sort chia dữ liệu vào nhiều xô theo khoảng rồi sắp từng xô; rất nhanh nếu dữ liệu phân bố đều, nhưng tệ nếu dồn cục vào một xô.
  • Bẫy thường gặp: dùng counting/radix cho dải giá trị mênh mông (như số 64-bit bất kỳ) → bộ nhớ nổ. Khi đó hãy quay về merge/quick sort.

6. Mẫu nhận diện​

  • Khóa là số nguyên nhỏ (tuổi, điểm 0–100, mã từ 0–9...) → counting sort.
  • Sắp số nhiều chữ số hoặc chuỗi độ dài cố định (mã bưu điện, biển số) → radix sort.
  • Số thực phân bố đều trong một khoảng (ví dụ 0.0–1.0) → bucket sort.
  • Thấy "dải giá trị nhỏ và biết trước" → nghĩ tới phi so sánh để đạt tuyến tính O(n + k).

7. 🎮 Trò chơi: Sắp xếp phi so sánh​

🎮 Counting · Radix · BucketCâu 1/4· Điểm 0· 🔥 0

Không so sánh phần tử — dùng giá trị làm địa chỉ. Vượt O(n log n) khi khóa nguyên dải hẹp.

Radix sort yêu cầu thuật toán đếm ở mỗi pha phải?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Độ phức tạp của counting sort là?
2. Khi nào KHÔNG nên dùng counting sort?
3. Radix sort xử lý số nhiều chữ số bằng cách?

9. Hoàn thành​

…

☑️ Tiếp theo: 3.2.1 — Tìm kiếm tuyến tính (bắt đầu chương tìm kiếm).