# Kĩ thuật Đếm Phân Phối theo cơ số 5
## 🎯 Mục tiêu chính
Sắp xếp một mảng số nguyên dương một cách ổn định và hiệu quả, bằng cách:
- Chuyển số thành cơ số 5 và xử lý từng chữ số từ **ít quan trọng nhất** đến **quan trọng nhất**
- Ở mỗi chữ số, **phân phối các phần tử** vào các nhóm (từ 0 đến 4) bằng **đếm phân phối**
- Kết quả cuối cùng là **mảng được sắp xếp đúng thứ tự**
### 📌 Tóm lại
Mục tiêu của đếm phân phối theo số mũ 5 là sắp xếp các số nguyên dương ổn định,hiệu quả, và theo từng chữ số trong hệ cơ số 5, bằng cách sử dụng phương pháp đếm phân phối lặp lại nhiều lần

## 📌 Dạng bài cần sử dụng đếm phân phối với cơ số 5
Đếm phân phối theo cơ số 5 thường được sử dụng trong các bài toán sắp xếp số nguyên dương hoặc chuỗi ký tự có giới hạn số lượng nhóm. Dưới đây là một số dạng bài toán điển hình:
### 🔹 Sắp xếp số nguyên dương có giá trị lớn
**📌 Dạng bài:**
- Cho một mảng số nguyên dương lớn (ví dụ: $0 -> 10^9$), yêu cầu sắp xếp

**📌 Khi nào chọn cơ số 5 ?**

- Khi muốn **giảm số nhóm** cần xử lý mỗi lần (chỉ có 5 nhóm thay vì 10 nhóm như mũ 10)
- Khi có **giới hạn bộ nhớ**, cơ số 5 giúp cân bằng giữa số lượng nhóm và số lần lặp.
**🔹 Ví dụ:**
- **Sắp xếp ID của các khách hàng** (ID rất lớn nhưng chỉ có một số mẫu nhất định)
- Sắp xếp các chỉ số lớn của các ngân hàng.

**Ưu điểm của đếm phân phối với cơ số 5 khi kết hợp với radix sort**
- ✅ Xử lý số lớn hơn bằng cách phân tách theo chữ số cơ số 5.
- ✅ Ổn định và tốc độ tốt khi dữ liệu có độ dài đồng đều.

**Nhược điểm**
- ❌ Bộ nhớ tốn kém nếu phạm vi quá rộng -> dễ xảy ra lỗi MLE

**Advices**
- 📌 Nếu dữ liệu rất lớn, nên chọn cơ số tối ưu hơn (ví dụ: 1024)
- Đếm phân phối với cơ số 5 hoạt động tốt khi kết hợp với radix sort hoặc merge sort
- Khi không kết hợp với radix sort hoặc merge sort thì khả năng bị tle sẽ tăng vì nó tương với hai vòng for $O(n^2)$

## Code sườn

FUNCTION COUNTING_SORT(arr, exp, base):
    Tạo mảng count[base] = 0
    Tạo mảng output có cùng kích thước arr
    
    // Đếm số lần xuất hiện của từng chữ số theo cơ số base
    FOR s IN arr:
        index = (s // exp) % base
        count[index] += 1

    // Tính vị trí thực của từng phần tử trong mảng đã sắp xếp
    FOR i FROM 1 TO base - 1:
        count[i] += count[i - 1]

    // Xếp các phần tử vào output theo thứ tự đã tính
    FOR i FROM LENGTH(arr) - 1 DOWNTO 0:
        index = (arr[i] // exp) % base
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    // copy output vào arr
    FOR i FROM 0 TO LENGTH(arr) - 1:
        arr[i] = output[i]

FUNCTION RADIX_SORT_BASE5(arr):
    IF arr RỖNG:
        RETURN arr
    max_s = GIÁ TRỊ LỚN NHẤT TRONG arr
    exp = 1 // Bắt đầu từ hàng đơn vị

    WHILE max_s // exp > 0:
        COUNTING_SORT(arr, exp, base=5)
        exp = exp * 5  // Chuyển sang chữ số tiếp theo trong hệ cơ số 5

    RETURN arr

## Độ phức tạp

- Đếm phân phối với cơ số 5 thường có độ phức tạp $O(n+k)$,trong đó $n$ là số phần tử và $k$ là phạm vi giá trị
- Trường hợp tệ nhất : Có thể có độ phức tạp lên đến $O(n^2)$ cần cân nhắc sử dụng các cơ số khác như (1024, 6, 9, ...)