Radix Sort & Counting Sort — Phá vỡ rào cản O(n log n)

Có một chứng minh toán học rằng mọi thuật toán sắp xếp dựa trên so sánh (comparison-based) không thể nhanh hơn O(n log n). Quick Sort, Merge Sort, Heap Sort — tất cả đều bị chặn bởi giới hạn này.

Nhưng Radix Sort và Counting Sort phá vỡ rào cản đó hoàn toàn. Bí quyết? Chúng không hề so sánh hai phần tử với nhau. Thay vào đó, chúng phân phối phần tử dựa trên giá trị trực tiếp. Khi dữ liệu có miền giá trị giới hạn, bạn có thể sắp xếp trong O(n). Điều này thay đổi cuộc chơi ở nhiều lĩnh vực thực tế — từ xử lý log, xây dựng database index, đến sắp xếp địa chỉ IP.

📘 Tại sao O(n log n) là giới hạn dưới?

Với n phần tử, có n! hoán vị khả dĩ. Mỗi phép so sánh chỉ loại bỏ tối đa 1/2 khả năng. Cần ít nhất log₂(n!) ≈ n log n phép so sánh để xác định đúng hoán vị. Non-comparison sort bypass hoàn toàn decision tree này.

Bức tranh tư duy

Counting Sort — Hộp thư được đánh số

Hãy tưởng tượng bạn là nhân viên bưu điện cần phân loại 1000 lá thư theo mã số từ 0 đến 9. Bạn không cần so sánh hai lá thư với nhau. Đặt 10 hộp thư trước mặt, đánh số 0–9. Cầm từng lá thư, đọc mã số, bỏ vào đúng hộp. Xong. Thu gom thư từ hộp 0 → hộp 9 là có kết quả sắp xếp.

Counting Sort hoạt động đúng như vậy: đếm số lần xuất hiện của mỗi giá trị, rồi đặt phần tử vào đúng vị trí.

Radix Sort — Phân loại theo từng chữ số

Bưu điện Việt Nam phân loại bưu kiện theo mã bưu chính 6 chữ số. Họ không so sánh toàn bộ mã một lần. Thay vào đó: phân loại theo chữ số cuối trước, rồi chữ số kế tiếp, cứ thế cho đến chữ số đầu tiên. Mỗi lượt phân loại chỉ cần 10 thùng (0–9).

Radix Sort áp dụng nguyên lý này: sắp xếp từng chữ số một, từ hàng đơn vị lên hàng cao nhất (LSD — Least Significant Digit). Điều kiện sống còn: mỗi lượt phân loại phải stable — giữ nguyên thứ tự tương đối của các phần tử có cùng chữ số.

Input:  [170, 045, 075, 090, 802, 024, 002, 066]

Lượt 1 — hàng đơn vị:  [170, 090, 802, 002, 024, 045, 075, 066]
Lượt 2 — hàng chục:    [802, 002, 024, 045, 066, 170, 075, 090]
Lượt 3 — hàng trăm:    [002, 024, 045, 066, 075, 090, 170, 802] ✅

Cốt lõi kỹ thuật

Counting Sort — Cơ chế hoạt động

Counting Sort gồm ba bước rõ ràng:

Bước 1 — Đếm tần suất: Duyệt mảng, đếm số lần xuất hiện của mỗi giá trị trong mảng count[].

Bước 2 — Prefix Sum: Biến đổi count[] thành mảng tổng tiền tố (prefix sum). Giá trị count[i] cho biết có bao nhiêu phần tử ≤ i. Đây chính là vị trí cuối cùng mà giá trị i sẽ đứng trong mảng kết quả.

Bước 3 — Xây dựng output: Duyệt mảng gốc từ phải sang trái. Với mỗi phần tử, tra count[] để biết vị trí, đặt vào output, giảm count[] đi 1. Duyệt ngược đảm bảo tính stable — phần tử xuất hiện sau giữ thứ tự sau.

Input: [4, 2, 2, 8, 3, 3, 1]     (n=7, k=9)

Bước 1 — Đếm:        count = [0, 1, 2, 1, 1, 0, 0, 0, 1]
                               0  1  2  3  4  5  6  7  8

Bước 2 — Prefix Sum:  count = [0, 1, 3, 4, 5, 5, 5, 5, 6]

Bước 3 — Đặt (phải→trái):
  arr[6]=1 → count[1]=1 → output[0]=1, count[1]=0
  arr[5]=3 → count[3]=4 → output[3]=3, count[3]=3
  arr[4]=3 → count[3]=3 → output[2]=3, count[3]=2
  ...
Output: [1, 2, 2, 3, 3, 4, 8] ✅

C++PythonJavaGo

cpp

#include <vector>
#include <algorithm>

std::vector<int> countingSort(const std::vector<int>& arr) {
    if (arr.empty()) return {};

    int maxVal = *std::max_element(arr.begin(), arr.end());
    int minVal = *std::min_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;

    std::vector<int> count(range, 0);
    std::vector<int> output(arr.size());

    // Bước 1: Đếm tần suất (dịch chuyển theo minVal để hỗ trợ số âm)
    for (int num : arr)
        count[num - minVal]++;

    // Bước 2: Prefix sum
    for (int i = 1; i < range; i++)
        count[i] += count[i - 1];

    // Bước 3: Xây dựng output (duyệt ngược → stable)
    for (int i = static_cast<int>(arr.size()) - 1; i >= 0; i--) {
        int idx = --count[arr[i] - minVal];
        output[idx] = arr[i];
    }
    return output;
}

python

def counting_sort(arr: list[int]) -> list[int]:
    """Counting Sort — Stable, O(n + k). Hỗ trợ số âm."""
    if not arr:
        return []

    min_val, max_val = min(arr), max(arr)
    k = max_val - min_val + 1

    count = [0] * k
    for num in arr:
        count[num - min_val] += 1

    # Prefix sum: count[i] = số phần tử <= i
    for i in range(1, k):
        count[i] += count[i - 1]

    output = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        val = arr[i]
        count[val - min_val] -= 1
        output[count[val - min_val]] = val

    return output

java

public class CountingSort {
    public static int[] sort(int[] arr) {
        if (arr.length == 0) return new int[0];

        int min = arr[0], max = arr[0];
        for (int num : arr) {
            if (num < min) min = num;
            if (num > max) max = num;
        }
        int range = max - min + 1;

        int[] count = new int[range];
        int[] output = new int[arr.length];

        for (int num : arr)
            count[num - min]++;

        for (int i = 1; i < range; i++)
            count[i] += count[i - 1];

        // Duyệt ngược để giữ tính stable
        for (int i = arr.length - 1; i >= 0; i--) {
            int idx = --count[arr[i] - min];
            output[idx] = arr[i];
        }
        return output;
    }
}

package sorting

func CountingSort(arr []int) []int {
    if len(arr) == 0 {
        return []int{}
    }

    minVal, maxVal := arr[0], arr[0]
    for _, v := range arr {
        if v < minVal { minVal = v }
        if v > maxVal { maxVal = v }
    }
    k := maxVal - minVal + 1

    count := make([]int, k)
    for _, v := range arr {
        count[v-minVal]++
    }

    for i := 1; i < k; i++ {
        count[i] += count[i-1]
    }

    output := make([]int, len(arr))
    for i := len(arr) - 1; i >= 0; i-- {
        count[arr[i]-minVal]--
        output[count[arr[i]-minVal]] = arr[i]
    }
    return output
}

Radix Sort — LSD và MSD

Radix Sort có hai biến thể chính:

LSD (Least Significant Digit): Sắp xếp từ chữ số ít quan trọng nhất (hàng đơn vị) đến quan trọng nhất. Mỗi lượt dùng một stable sort phụ trợ (thường là Counting Sort). Đơn giản, dễ cài đặt, phù hợp với số nguyên và chuỗi có cùng độ dài.

MSD (Most Significant Digit): Sắp xếp từ chữ số quan trọng nhất. Sau mỗi lượt, chia thành các nhóm con và đệ quy. Phù hợp với chuỗi có độ dài khác nhau (tự dừng sớm khi nhóm chỉ còn 1 phần tử). Tuy nhiên cài đặt phức tạp hơn đáng kể.

⚠️ Tính stable là bắt buộc

Nếu subroutine sort ở mỗi lượt KHÔNG stable, thứ tự từ các lượt trước sẽ bị phá vỡ → kết quả sai. Đây là lý do Counting Sort (stable) được dùng làm subroutine, không phải Quick Sort (unstable).

C++PythonJavaGo

cpp

#include <vector>
#include <algorithm>

void countingSortByDigit(std::vector<int>& arr, int exp) {
    int n = arr.size();
    std::vector<int> output(n);
    int count[10] = {0};

    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[--count[digit]] = arr[i];
    }
    arr = output;
}

void radixSort(std::vector<int>& arr) {
    if (arr.empty()) return;

    int maxVal = *std::max_element(arr.begin(), arr.end());

    // Xử lý từng chữ số: 1, 10, 100, ...
    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countingSortByDigit(arr, exp);
}

python

def radix_sort(arr: list[int]) -> list[int]:
    """LSD Radix Sort — O(d * (n + k)) với base 10."""
    if not arr:
        return []

    max_val = max(arr)
    result = arr[:]
    exp = 1  # 1, 10, 100, ...

    while max_val // exp > 0:
        # Counting sort theo chữ số tại vị trí exp
        count = [0] * 10
        output = [0] * len(result)

        for num in result:
            count[(num // exp) % 10] += 1

        for i in range(1, 10):
            count[i] += count[i - 1]

        # Duyệt ngược → stable
        for i in range(len(result) - 1, -1, -1):
            digit = (result[i] // exp) % 10
            count[digit] -= 1
            output[count[digit]] = result[i]

        result = output
        exp *= 10

    return result

java

public class RadixSort {
    public static void sort(int[] arr) {
        if (arr.length == 0) return;

        int max = arr[0];
        for (int num : arr)
            if (num > max) max = num;

        for (int exp = 1; max / exp > 0; exp *= 10)
            countingSortByDigit(arr, exp);
    }

    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];

        for (int num : arr)
            count[(num / exp) % 10]++;

        for (int i = 1; i < 10; i++)
            count[i] += count[i - 1];

        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[--count[digit]] = arr[i];
        }
        System.arraycopy(output, 0, arr, 0, n);
    }
}

package sorting

func RadixSort(arr []int) {
    if len(arr) == 0 {
        return
    }

    maxVal := arr[0]
    for _, v := range arr {
        if v > maxVal { maxVal = v }
    }

    for exp := 1; maxVal/exp > 0; exp *= 10 {
        countingSortByDigit(arr, exp)
    }
}

func countingSortByDigit(arr []int, exp int) {
    n := len(arr)
    output := make([]int, n)
    count := make([]int, 10)

    for _, v := range arr {
        count[(v/exp)%10]++
    }
    for i := 1; i < 10; i++ {
        count[i] += count[i-1]
    }
    for i := n - 1; i >= 0; i-- {
        digit := (arr[i] / exp) % 10
        count[digit]--
        output[count[digit]] = arr[i]
    }
    copy(arr, output)
}

Tối ưu Radix Sort — Base 256

Với số nguyên 32-bit, dùng base 10 cần tối đa 10 lượt (10 chữ số). Nếu chuyển sang base 256 (xử lý theo từng byte), chỉ cần 4 lượt cho 32-bit. Đánh đổi: mảng count[] tăng từ 10 lên 256 phần tử — hoàn toàn chấp nhận được.

python

def radix_sort_base256(arr: list[int]) -> list[int]:
    """Radix Sort base 256 — chỉ 4 lượt cho 32-bit integer."""
    if not arr:
        return []

    result = arr[:]
    for byte_idx in range(4):
        count = [0] * 256
        output = [0] * len(result)
        shift = byte_idx * 8

        for num in result:
            count[(num >> shift) & 0xFF] += 1

        for i in range(1, 256):
            count[i] += count[i - 1]

        for i in range(len(result) - 1, -1, -1):
            byte_val = (result[i] >> shift) & 0xFF
            count[byte_val] -= 1
            output[count[byte_val]] = result[i]

        result = output
    return result

Bucket Sort — Người anh em phân phối

Bucket Sort chia phần tử vào các bucket (thùng) dựa trên miền giá trị, sắp xếp từng bucket riêng (bằng Insertion Sort hoặc sort khác), rồi ghép lại. Hiệu quả nhất khi dữ liệu phân bố đều — đạt O(n) trung bình. Với dữ liệu phân bố lệch, hiệu suất giảm về O(n²) khi tất cả rơi vào một bucket.

Thực chiến

Sắp xếp địa chỉ IP

Địa chỉ IPv4 có 4 octet, mỗi octet từ 0–255. Chuyển thành số nguyên 32-bit rồi dùng Radix Sort base 256 — chỉ cần 4 lượt, mỗi lượt xử lý 1 octet.

python

def sort_ip_addresses(ips: list[str]) -> list[str]:
    """Sắp xếp danh sách IP bằng Radix Sort — O(n)."""
    def ip_to_int(ip: str) -> int:
        parts = ip.split(".")
        return (int(parts[0]) << 24 | int(parts[1]) << 16
                | int(parts[2]) << 8 | int(parts[3]))

    def int_to_ip(val: int) -> str:
        return f"{(val>>24)&0xFF}.{(val>>16)&0xFF}.{(val>>8)&0xFF}.{val&0xFF}"

    int_ips = [ip_to_int(ip) for ip in ips]
    sorted_ints = radix_sort_base256(int_ips)
    return [int_to_ip(v) for v in sorted_ints]

# Ví dụ
ips = ["192.168.1.10", "10.0.0.1", "172.16.0.5", "10.0.0.2"]
print(sort_ip_addresses(ips))
# → ["10.0.0.1", "10.0.0.2", "172.16.0.5", "192.168.1.10"]

Sắp xếp log entry theo timestamp

Hệ thống log với timestamp dạng YYYYMMDD-HHmmss. Mỗi thành phần (năm, tháng, ngày, giờ, phút, giây) có miền giá trị nhỏ — lý tưởng cho Radix Sort theo từng thành phần.

python

def sort_logs_by_timestamp(logs: list[dict]) -> list[dict]:
    """Sắp xếp log theo timestamp dùng Radix Sort multi-key."""
    # Sắp xếp theo key ít quan trọng nhất trước (LSD logic)
    keys = ["second", "minute", "hour", "day", "month", "year"]
    ranges = [60, 60, 24, 32, 13, 10000]

    result = logs[:]
    for key, k in zip(keys, ranges):
        count = [0] * k
        output = [None] * len(result)

        for log in result:
            count[log[key]] += 1
        for i in range(1, k):
            count[i] += count[i - 1]
        for i in range(len(result) - 1, -1, -1):
            val = result[i][key]
            count[val] -= 1
            output[count[val]] = result[i]

        result = output
    return result

Xây dựng database index

Trong database engine, xây dựng B-tree index trên cột integer thường bắt đầu bằng sắp xếp tất cả (key, rowid) — sau đó bulk-load vào B-tree. Radix Sort cho bước sắp xếp này nhanh hơn comparison sort khi số lượng row lớn và key là integer.

Suffix Array Construction

Suffix array — cấu trúc dữ liệu nền tảng cho full-text search — có thể xây dựng trong O(n) bằng SA-IS algorithm, trong đó Radix Sort được dùng để sắp xếp các suffix theo ký tự. Tính stable của Radix Sort là yếu tố then chốt giúp thuật toán hoạt động đúng.

Sai lầm điển hình

Sai lầm 1 — Dùng Counting Sort với miền giá trị khổng lồ

python

# ❌ SAI: miền giá trị 10^9 → cấp phát mảng 1 tỷ phần tử
arr = [1, 1000000000, 5, 999999999]
count = [0] * (max(arr) + 1)  # 4GB RAM chỉ cho mảng count!

python

# ✅ ĐÚNG: Khi k >> n, dùng Radix Sort hoặc comparison sort
arr = [1, 1000000000, 5, 999999999]
result = radix_sort(arr)  # Chỉ cần O(n) space, 10 lượt

Quy tắc: Counting Sort hiệu quả khi k = O(n). Nếu k >> n, memory sẽ bùng nổ.

Sai lầm 2 — Quên yêu cầu stable cho Radix Sort

python

# ❌ SAI: Dùng unstable sort làm subroutine
def radix_sort_broken(arr):
    for exp in [1, 10, 100]:
        arr.sort(key=lambda x: (x // exp) % 10)
        # Python's sort là stable → tình cờ đúng
        # Nhưng nếu dùng Quick Sort (unstable) → KẾT QUẢ SAI

Giải thích: Ở lượt thứ 2, các phần tử cùng chữ số hàng chục phải giữ nguyên thứ tự từ lượt 1 (hàng đơn vị). Nếu subroutine unstable, thứ tự này bị phá vỡ → toàn bộ thuật toán sai.

Sai lầm 3 — Không xử lý số âm

python

# ❌ SAI: Radix Sort cơ bản chỉ xử lý số không âm
arr = [170, -45, 75, -90]
radix_sort(arr)  # Kết quả sai hoặc crash

python

# ✅ ĐÚNG: Tách số âm và dương, xử lý riêng
def radix_sort_with_negatives(arr: list[int]) -> list[int]:
    negatives = [-x for x in arr if x < 0]
    positives = [x for x in arr if x >= 0]

    sorted_neg = radix_sort(negatives)[::-1]  # Đảo ngược
    sorted_neg = [-x for x in sorted_neg]
    sorted_pos = radix_sort(positives)

    return sorted_neg + sorted_pos

Sai lầm 4 — Nhầm lẫn độ phức tạp

❌ "Radix Sort là O(n)" → Thiếu!
✅ "Radix Sort là O(d × (n + k))" với:
   - d = số chữ số (hoặc số byte)
   - k = base (10, 256, ...)
   - n = số phần tử

Khi d và k là hằng số (ví dụ: 32-bit int, base 256 → d=4, k=256),
thì O(d × (n + k)) = O(4 × (n + 256)) = O(n).
Nhưng khi d = log n (số có n chữ số), thì O(d × n) = O(n log n)
→ KHÔNG còn lợi thế so với comparison sort.

Under the Hood

Phân tích độ phức tạp

Thuật toán	Thời gian	Bộ nhớ phụ	Stable	In-place
Counting Sort	O(n + k)	O(n + k)	✅	❌
Radix Sort (base b)	O(d × (n + b))	O(n + b)	✅	❌
Bucket Sort	O(n) trung bình	O(n + k)	✅	❌
Merge Sort	O(n log n)	O(n)	✅	❌
Quick Sort	O(n log n) trung bình	O(log n)	❌	✅

Counting Sort: Duyệt mảng 2 lần (đếm + đặt) + duyệt count[] 1 lần → O(n + k). Space cho count[] là O(k), cho output[] là O(n) → tổng O(n + k).

Radix Sort: Thực hiện d lượt, mỗi lượt là Counting Sort O(n + b) với b là base → tổng O(d × (n + b)). Với 32-bit integer base 256: d = 4, b = 256 → O(4n + 1024) = O(n).

Khi nào comparison sort thắng?

Radix/Counting Sort không phải lúc nào cũng nhanh hơn:

n nhỏ (< 1000): Overhead của Counting Sort (cấp phát mảng count[], prefix sum) lớn hơn lợi ích. Insertion Sort hoặc std::sort nhanh hơn nhờ cache-friendly.

k quá lớn so với n: Counting Sort với k = 10⁹ nhưng n = 100 → lãng phí bộ nhớ khổng lồ. Comparison sort chỉ cần O(n log n) = O(700) phép toán.

Dữ liệu không phải integer: Floating point, string dài không đều, object phức tạp — comparison sort linh hoạt hơn.

Framework quyết định

Chứng minh giới hạn O(n log n) — Phác thảo

Mọi comparison sort có thể biểu diễn bằng decision tree — cây nhị phân trong đó mỗi nút là một phép so sánh. Với n phần tử, có n! hoán vị (permutation) → cây cần ít nhất n! lá. Chiều cao tối thiểu của cây nhị phân có L lá là ⌈log₂ L⌉.

Do đó: chiều cao ≥ log₂(n!) ≈ n log n (theo xấp xỉ Stirling).

Mỗi đường đi từ gốc đến lá là một chuỗi so sánh → worst case cần ít nhất Ω(n log n) phép so sánh. Non-comparison sort thoát khỏi giới hạn này vì chúng không đi theo decision tree — chúng dùng giá trị trực tiếp làm index.

Checklist ghi nhớ

✅ Checklist triển khai

Counting Sort

[ ] Đếm tần suất → prefix sum → đặt phần tử (3 bước)
[ ] Duyệt ngược (phải → trái) ở bước 3 để giữ tính stable
[ ] Chỉ hiệu quả khi k = O(n) — miền giá trị tỷ lệ với số phần tử
[ ] Hỗ trợ số âm bằng cách dịch chuyển min_val về 0

Radix Sort

[ ] LSD: chữ số ít quan trọng nhất trước → cần stable subroutine
[ ] MSD: chữ số quan trọng nhất trước → đệ quy theo nhóm
[ ] Base 256 (xử lý theo byte) giảm số lượt từ 10 xuống 4 cho 32-bit
[ ] Tính stable của subroutine là bắt buộc — không stable = sai kết quả

Độ phức tạp & lựa chọn

[ ] Counting Sort: O(n + k) time, O(n + k) space
[ ] Radix Sort: O(d × (n + b)) — d là số chữ số, b là base
[ ] Giới hạn O(n log n) chỉ áp dụng cho comparison sort (decision tree argument)
[ ] Khi n nhỏ hoặc k >> n, comparison sort thường nhanh hơn trong thực tế

Bài tập luyện tập

Bài 1 — Counting Sort cho điểm thi (Foundation)

Cho mảng scores[] chứa điểm thi của n sinh viên, mỗi điểm từ 0 đến 100. Sắp xếp mảng bằng Counting Sort. Ngoài ra, trả về mảng rank[] trong đó rank[i] là thứ hạng (1-indexed) của sinh viên thứ i.

💡 Gợi ý

Miền giá trị k = 101 (0–100) → Counting Sort lý tưởng
Dùng prefix sum để tính rank: phần tử có giá trị v đứng ở vị trí count[v-1]+1 đến count[v]

✅ Lời giải

python

def sort_scores_with_rank(scores: list[int]) -> tuple[list[int], list[int]]:
    n = len(scores)
    count = [0] * 101

    for s in scores:
        count[s] += 1

    # Prefix sum
    for i in range(1, 101):
        count[i] += count[i - 1]

    sorted_arr = [0] * n
    original_rank = [0] * n

    for i in range(n - 1, -1, -1):
        count[scores[i]] -= 1
        pos = count[scores[i]]
        sorted_arr[pos] = scores[i]
        original_rank[i] = pos + 1  # 1-indexed rank

    return sorted_arr, original_rank

Phân tích: Time O(n + 101) = O(n). Space O(n + 101) = O(n).

Bài 2 — Radix Sort cho số điện thoại (Intermediate)

Cho danh sách n số điện thoại Việt Nam dạng "0912345678" (10 chữ số). Sắp xếp toàn bộ danh sách bằng Radix Sort. Yêu cầu: O(n) thời gian và tính stable.

💡 Gợi ý

Mỗi số điện thoại có đúng 10 chữ số → LSD Radix Sort với 10 lượt
Hoặc chuyển thành integer 64-bit rồi dùng Radix Sort base 256 (5 lượt cho 40-bit)

✅ Lời giải

python

def sort_phone_numbers(phones: list[str]) -> list[str]:
    """LSD Radix Sort cho số điện thoại 10 chữ số."""
    result = phones[:]

    # 10 lượt, từ chữ số cuối (index 9) → đầu (index 0)
    for pos in range(9, -1, -1):
        count = [0] * 10
        output = [""] * len(result)

        for phone in result:
            digit = int(phone[pos])
            count[digit] += 1

        for i in range(1, 10):
            count[i] += count[i - 1]

        for i in range(len(result) - 1, -1, -1):
            digit = int(result[i][pos])
            count[digit] -= 1
            output[count[digit]] = result[i]

        result = output
    return result

Phân tích: 10 lượt × O(n + 10) mỗi lượt = O(10n) = O(n). Stable vì Counting Sort stable.

Bài 3 — Maximum Gap (Advanced)

Cho mảng n số nguyên không âm, tìm khoảng cách lớn nhất giữa hai phần tử liên tiếp trong mảng đã sắp xếp. Yêu cầu: O(n) thời gian và O(n) bộ nhớ. (LeetCode 164)

💡 Gợi ý

Dùng Radix Sort để sắp xếp trong O(n), rồi duyệt tìm max gap
Hoặc dùng Bucket Sort / Pigeonhole principle: chia thành n-1 bucket, max gap chắc chắn nằm giữa hai bucket khác nhau (không nằm trong cùng bucket)

✅ Lời giải

python

def maximum_gap(nums: list[int]) -> int:
    if len(nums) < 2:
        return 0

    min_val, max_val = min(nums), max(nums)
    if min_val == max_val:
        return 0

    n = len(nums)
    bucket_size = max(1, (max_val - min_val) // (n - 1))
    bucket_count = (max_val - min_val) // bucket_size + 1

    # Mỗi bucket lưu (min, max) — gap tối đa nằm giữa các bucket
    buckets = [[float('inf'), float('-inf')] for _ in range(bucket_count)]

    for num in nums:
        idx = (num - min_val) // bucket_size
        buckets[idx][0] = min(buckets[idx][0], num)
        buckets[idx][1] = max(buckets[idx][1], num)

    max_gap = 0
    prev_max = min_val
    for lo, hi in buckets:
        if lo == float('inf'):
            continue  # bucket rỗng
        max_gap = max(max_gap, lo - prev_max)
        prev_max = hi

    return max_gap

Phân tích: Time O(n), Space O(n). Pigeonhole principle đảm bảo max gap không thể nằm bên trong một bucket → chỉ cần so sánh giữa các bucket.

🧠 Quiz

Câu hỏi kiểm tra: Radix Sort (LSD) với base 10 trên mảng n số nguyên 32-bit có độ phức tạp thời gian là gì?

[ ] A. O(n) — vì không so sánh phần tử
[ ] B. O(n log n) — giống comparison sort
[x] C. O(d × (n + 10)) với d ≤ 10 — tuyến tính khi d là hằng số
[ ] D. O(n × k) — với k là giá trị lớn nhất trong mảng

Giải thích: Radix Sort thực hiện d lượt Counting Sort, mỗi lượt O(n + b) với b = base. Với base 10 và 32-bit integer, d ≤ 10 → O(10 × (n + 10)) = O(n). Đáp án A thiếu yếu tố d. Đáp án B nhầm với comparison sort. Đáp án D nhầm k (range) với base — Counting Sort phụ thuộc base, không phải giá trị max.

Liên kết học tiếp

Từ khóa glossary: Counting Sort, Radix Sort, Bucket Sort, Non-comparison Sort, Distribution Sort, Prefix Sum, Stable Sort

Tìm kiếm liên quan: sắp xếp tuyến tính, sắp xếp không so sánh, radix sort là gì

Radix Sort & Counting Sort — Phá vỡ rào cản O(n log n) ​

Bức tranh tư duy ​

Counting Sort — Hộp thư được đánh số ​

Radix Sort — Phân loại theo từng chữ số ​

Cốt lõi kỹ thuật ​

Counting Sort — Cơ chế hoạt động ​

Radix Sort — LSD và MSD ​

Tối ưu Radix Sort — Base 256 ​

Bucket Sort — Người anh em phân phối ​

Thực chiến ​

Sắp xếp địa chỉ IP ​

Sắp xếp log entry theo timestamp ​

Xây dựng database index ​

Suffix Array Construction ​

Sai lầm điển hình ​

Sai lầm 1 — Dùng Counting Sort với miền giá trị khổng lồ ​

Sai lầm 2 — Quên yêu cầu stable cho Radix Sort ​

Sai lầm 3 — Không xử lý số âm ​

Sai lầm 4 — Nhầm lẫn độ phức tạp ​

Under the Hood ​

Phân tích độ phức tạp ​

Khi nào comparison sort thắng? ​

Framework quyết định ​

Chứng minh giới hạn O(n log n) — Phác thảo ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1 — Counting Sort cho điểm thi (Foundation) ​

Bài 2 — Radix Sort cho số điện thoại (Intermediate) ​

Bài 3 — Maximum Gap (Advanced) ​

Liên kết học tiếp ​

Radix Sort & Counting Sort — Phá vỡ rào cản O(n log n)

Bức tranh tư duy

Counting Sort — Hộp thư được đánh số

Radix Sort — Phân loại theo từng chữ số

Cốt lõi kỹ thuật

Counting Sort — Cơ chế hoạt động

Radix Sort — LSD và MSD

Tối ưu Radix Sort — Base 256

Bucket Sort — Người anh em phân phối

Thực chiến

Sắp xếp địa chỉ IP

Sắp xếp log entry theo timestamp

Xây dựng database index

Suffix Array Construction

Sai lầm điển hình

Sai lầm 1 — Dùng Counting Sort với miền giá trị khổng lồ

Sai lầm 2 — Quên yêu cầu stable cho Radix Sort

Sai lầm 3 — Không xử lý số âm

Sai lầm 4 — Nhầm lẫn độ phức tạp

Under the Hood

Phân tích độ phức tạp

Khi nào comparison sort thắng?

Framework quyết định

Chứng minh giới hạn O(n log n) — Phác thảo

Checklist ghi nhớ

Bài tập luyện tập

Bài 1 — Counting Sort cho điểm thi (Foundation)

Bài 2 — Radix Sort cho số điện thoại (Intermediate)

Bài 3 — Maximum Gap (Advanced)

Liên kết học tiếp