Counting / Radix / Bucket sort — Non-comparison O(n) khi key range nhỏ

Lesson 01 của Module 4 đã chứng minh lower bound n log n cho mọi comparison sort — không có cách nào tốt hơn khi chỉ dùng phép so sánh. Nhưng nếu cần sort 100 triệu bản ghi int trong range 0 đến 1000 thì sao? Counting sort chạy O(n + k) với k = 1001 — tức là O(n), không phụ thuộc n log n.

Điểm mấu chốt: lower bound đó chỉ áp dụng cho comparison-based sort. Khi biết thêm thông tin về key — range nhỏ, số digit cố định, hay distribution đồng đều — có thể bypass phép so sánh hoàn toàn và đạt tốc độ nhanh hơn.

Bài này dạy 3 non-comparison sort: Counting sort (range nhỏ), Radix sort LSD/MSD (fixed-width key), và Bucket sort (uniform distribution). Bao gồm khi nào pick từng loại và cảnh báo về memory cost.

1. Analogy — Sắp bài theo suit

Hình dung một bộ bài 52 lá cần sắp theo suit: cơ, rô, nhép, bích.

Nếu dùng comparison sort: cầm hai lá, so sánh, đặt lá nhỏ hơn sang trái — lặp lại đến khi xong. Mỗi bước tốn 1 phép so sánh.

Nếu dùng non-comparison sort: đặt sẵn 4 ô trên bàn, mỗi ô là 1 suit. Nhặt từng lá, nhìn suit, bỏ thẳng vào ô đúng — không cần so sánh lá nào với lá nào. Hết bài thì đọc theo thứ tự ô. Nhanh hơn vì biết trước chỉ có 4 suit.

2. Counting sort

2.1 Cơ chế

Cho array các số nguyên trong range [0, k). Ba bước:

1. Count: đếm tần suất mỗi giá trị vào count[0..k-1].
2. Prefix sum: biến count[i] thành số lượng element có giá trị nhỏ hơn hoặc bằng i — đây là vị trí cuối của giá trị i trong output.
3. Place (right-to-left): duyệt array gốc từ phải sang trái, đặt từng element vào đúng vị trí trong output.

public static void countingSort(int[] arr, int k) {
    // arr values in [0, k)
    int[] count = new int[k];
    for (int x : arr) count[x]++;

    // prefix sum -> count[i] = position in output (exclusive upper bound)
    for (int i = 1; i < k; i++) count[i] += count[i - 1];

    // place from right to left for stability
    int[] output = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        output[--count[arr[i]]] = arr[i];
    }
    System.arraycopy(output, 0, arr, 0, arr.length);
}

2.2 Trace ví dụ

Sort [4, 2, 2, 8, 3, 3, 1] với k = 10:

Input:       [4, 2, 2, 8, 3, 3, 1]

Count step:
  count[0]=0, count[1]=1, count[2]=2, count[3]=2
  count[4]=1, count[5..7]=0, count[8]=1

Prefix sum:
  count[0]=0, count[1]=1, count[2]=3, count[3]=5
  count[4]=6, count[5..7]=6, count[8]=7

Place right-to-left:
  i=6: arr[6]=1 -> output[--count[1]] = output[0] = 1
  i=5: arr[5]=3 -> output[--count[3]] = output[4] = 3
  i=4: arr[4]=3 -> output[--count[3]] = output[3] = 3
  i=3: arr[3]=8 -> output[--count[8]] = output[6] = 8
  i=2: arr[2]=2 -> output[--count[2]] = output[2] = 2
  i=1: arr[1]=2 -> output[--count[2]] = output[1] = 2
  i=0: arr[0]=4 -> output[--count[4]] = output[5] = 4

Output: [1, 2, 2, 3, 3, 4, 8]

2.3 Properties

Vì sao right-to-left đảm bảo stability? Khi duyệt từ phải sang trái, element xuất hiện sau trong input được đặt vào ô cuối cùng còn trống cho giá trị đó. Element xuất hiện trước được đặt vào ô trước đó. Thứ tự tương đối của các element bằng nhau được bảo toàn.

3. Radix sort (LSD — Least Significant Digit first)

3.1 Ý tưởng

Counting sort đòi hỏi k nhỏ. Với số nguyên 32-bit, k có thể lên tới hàng tỉ — không thực tế. Radix sort xử lý từng chữ số (digit) riêng biệt, mỗi lần Counting sort theo digit đó.

LSD (Least Significant Digit): bắt đầu từ chữ số ít quan trọng nhất (hàng đơn vị), sort theo đó, rồi tiến dần lên hàng chục, hàng trăm... LSD đòi hỏi sub-sort stable để các chữ số trước không bị phá vỡ khi sort chữ số sau.

public static void radixSortLSD(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}

private static void countingSortByDigit(int[] arr, int exp) {
    int[] count = new int[10];
    for (int x : arr) count[(x / exp) % 10]++;
    for (int i = 1; i < 10; i++) count[i] += count[i - 1];
    int[] output = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        int d = (arr[i] / exp) % 10;
        output[--count[d]] = arr[i];
    }
    System.arraycopy(output, 0, arr, 0, arr.length);
}

3.2 Trace ví dụ

Sort [170, 45, 75, 90, 802, 24, 2, 66]:

exp=1 (units digit):
  Input:  [170, 45, 75, 90, 802, 24, 2, 66]
  Digits: [  0,  5,  5,  0,   2,  4, 2,  6]
  After:  [170, 90, 802, 2, 24, 45, 75, 66]

exp=10 (tens digit):
  Input:  [170, 90, 802, 2, 24, 45, 75, 66]
  Digits: [  7,  9,   0, 0,  2,  4,  7,  6]
  After:  [802, 2, 24, 45, 66, 170, 75, 90]

exp=100 (hundreds digit):
  Input:  [802, 2, 24, 45, 66, 170, 75, 90]
  Digits: [  8, 0,  0,  0,  0,   1,  0,  0]
  After:  [2, 24, 45, 66, 75, 90, 170, 802]

3.3 Properties và variant

MSD (Most Significant Digit first): bắt đầu từ chữ số quan trọng nhất. Xử lý đệ quy theo bucket — phù hợp cho variable-length string và khi muốn early termination. Phức tạp hơn LSD vì cần quản lý recursive bucket riêng cho từng prefix.

Base lớn hơn = ít pass hơn: thay vì base 10 (10 digits, d = 10 cho 10-tỉ), dùng base 256 (1 byte = 1 digit, d = 4 pass cho 32-bit int). Mỗi pass tốn O(n + 256) thay O(n + 10) — tổng nhanh hơn về constant.

4. Bucket sort

4.1 Ý tưởng

Bucket sort phù hợp khi data có uniform distribution trên một range đã biết. Chia range thành k bucket đều nhau, distribute từng element vào bucket tương ứng, sort từng bucket bằng comparison sort, rồi concat.

public static void bucketSort(double[] arr, int bucketCount) {
    // arr values in [0.0, 1.0)
    @SuppressWarnings("unchecked")
    List<Double>[] buckets = new List[bucketCount];
    for (int i = 0; i < bucketCount; i++) {
        buckets[i] = new ArrayList<>();
    }

    // distribute: element x goes into bucket floor(x * bucketCount)
    for (double x : arr) {
        int idx = (int) (x * bucketCount);
        buckets[idx].add(x);
    }

    // sort each bucket (insertion sort wins for small buckets)
    int pos = 0;
    for (List<Double> bucket : buckets) {
        Collections.sort(bucket);
        for (double x : bucket) arr[pos++] = x;
    }
}

4.2 Phân tích

Best case (uniform distribution): mỗi bucket nhận xấp xỉ n/k element. Sort từng bucket tốn O((n/k) log(n/k)). Tổng: O(n + k × (n/k) log(n/k)) = O(n + n log(n/k)). Khi k = n, O(n) — tuyến tính.

Worst case (skewed distribution): toàn bộ element rơi vào 1 bucket. Sort bucket đó tốn O(n log n) — degenerate về comparison sort.

5. Bảng so sánh đầy đủ

Cột Time dùng ký hiệu ngắn (không có backtick) để tránh vỡ bảng:

6. Vì sao non-comparison sort không phá lower bound n log n

Lower bound n log n chỉ áp dụng cho comparison-based sort — chứng minh qua decision tree với n! permutation (xem Module 4 lesson 01).

Non-comparison sort không tạo decision tree so sánh — thay vào đó dùng assumption thêm về input:

• Counting sort: key nằm trong range nhỏ [0, k) — dùng key làm index trực tiếp.
• Radix sort: key có số digit d cố định — xử lý từng digit độc lập.
• Bucket sort: distribution gần uniform — phân bổ đều vào bucket.

Khi assumption đó sai (k lớn, d lớn, distribution skewed), non-comparison sort không còn hiệu quả hơn — hoặc thậm chí tệ hơn về space và worst case.

Trade-off: thêm space + giả định về input, đổi lấy tốc độ tốt hơn. Đây không phải "phá" lower bound — mà là thay đổi bài toán: từ "sort bất kỳ data" thành "sort data có cấu trúc đặc biệt".

7. Pitfall tổng hợp

Pitfall 1 — Counting sort với range lớn: OOM

// WRONG: k = Integer.MAX_VALUE -> allocate 2GB array -> OOM
int[] arr = {Integer.MAX_VALUE - 1, 0, 5};
int k = Integer.MAX_VALUE;
int[] count = new int[k];  // OutOfMemoryError

Counting sort chỉ thực tế khi k = O(n) hoặc nhỏ hơn. Với array 1 triệu phần tử, k hợp lý là dưới vài triệu. Nếu range lớn, dùng Radix sort (chia nhỏ key thành digit) thay Counting sort trực tiếp.

// Check before allocating: if k >> n, consider radix sort instead
int min = Arrays.stream(arr).min().getAsInt();
int max = Arrays.stream(arr).max().getAsInt();
long range = (long) max - min + 1;
if (range > 10L * arr.length) {
    // range too large for counting sort -- use radix or comparison sort
    Arrays.sort(arr);
} else {
    countingSort(arr, (int) range, min);
}

Pitfall 2 — Radix sort cho variable-length string: thứ tự sai

LSD Radix sort giả định mọi key có cùng độ dài. Với string có độ dài khác nhau, cần padding bằng null character hay space — nhưng padding gây ra vấn đề: lexicographic order với null padding khác natural order.

Input strings: ["car", "cat", "a", "be"]
Pad to length 3: ["car", "cat", "a  ", "be "]  <- space padding
LSD result might differ from natural sort depending on how spaces compare

Safe approach: use MSD radix sort (handles variable length natively)
or use comparison sort with standard String.compareTo()

Với variable-length string trong production: ưu tiên MSD radix hoặc Counting sort theo ký tự từng level. Hoặc đơn giản là dùng Arrays.sort(String[]) (TimSort) nếu không có bottleneck thực sự đo được.

Pitfall 3 — Bucket sort với non-uniform distribution

// If all values cluster near 0.01, they all fall into bucket 0
double[] arr = {0.001, 0.005, 0.003, 0.007, 0.002, 0.8, 0.9};
// Buckets of size 0.1: almost all elements in bucket 0
// -> O(n log n) for that one bucket -> no gain over comparison sort

Đo distribution trước khi dùng Bucket sort. Nếu data có pattern (log-normal, Zipfian, power-law), cần thiết kế bucket boundary theo distribution thực tế thay vì chia đều. Hoặc chuyển sang Counting/Radix sort nếu key có thể map sang integer.

8. Java standard library và production note

Arrays.sort(int[]) Java không dùng Counting hay Radix sort mặc định — dùng Dual-Pivot Quicksort. Lý do: Arrays.sort nhận mảng tùy ý, không biết trước key range. Non-comparison sort đòi hỏi programmer cung cấp thêm context (k, digit count, distribution) — JDK không thể đoán.

// JDK default: Dual-Pivot Quicksort
int[] arr = {5, 3, 8, 1, 9};
Arrays.sort(arr);  // O(n log n), không phải O(n+k)

// If you know range is small, implement counting sort manually:
// countingSort(arr, maxValue + 1);

Ngoài JDK:

• Apache Commons Primitives / Eclipse Collections: cung cấp SortedLists với Radix sort option cho int[] và long[].
• fastutil library: IntArrays.radixSort(int[]) — LSD radix sort cho primitive int, thực tế nhanh hơn Arrays.sort khoảng 2-3x trên large random int array.
• Chrome V8 engine: sort array số nguyên nhỏ trong JavaScript dùng Counting sort variant khi detect range phù hợp.

9. Ứng dụng thực tế

Database aggregation — GROUP BY với integer key: khi aggregate COUNT(*) theo http_status_code (range 100-599), database engine hiệu quả nhất là giữ counting array kích thước 600 — đây chính là Counting sort structure. Tổng O(n) thay vì O(n log n) cho sort-then-group.

Histograms — log buckets HTTP status: monitoring system thống kê phân phối HTTP response code (2xx/3xx/4xx/5xx) từ hàng triệu request log. Range chỉ 600 giá trị → Counting sort O(n) để sort + aggregate trong một pass, không cần comparison sort nào.

Networking — packet sort theo IP prefix: router sort gói tin theo destination IP để longest-prefix-match. Địa chỉ IP 32-bit gồm 4 octet → Radix sort 4 phase, mỗi phase Counting sort theo 1 byte (base 256, k=256). Tổng: O(4n) = O(n), nhanh hơn comparison sort với n vài triệu gói tin/giây.

Graphics rendering — depth sort (painters algorithm): để render overlapping object theo thứ tự front-to-back, Bucket sort chia z-range thành k bucket. Với uniform object distribution, mỗi bucket nhận vài object, sort từng bucket bằng Insertion sort, concat → O(n + k) expected. Dùng cho game engine offline rendering pass.

10. Deep Dive

11. Tóm tắt

• Lower bound n log n áp dụng cho comparison sort — non-comparison sort bypass bằng cách dùng thêm assumption về input (range, digit count, distribution).
• Counting sort O(n + k): đếm tần suất, prefix sum, place right-to-left. Stable. Chỉ dùng khi k = O(n) hoặc nhỏ hơn — k lớn gây OOM.
• Radix LSD O(n × d): sort từng digit từ phải sang trái bằng Counting sort stable. Hiệu quả cho fixed-width key: 32-bit int (d=4 với base 256), fixed-length string.
• MSD Radix: sort từ digit quan trọng nhất, xử lý đệ quy — phù hợp variable-length string, cho phép early termination.
• Bucket sort O(n + k) expected: distribute vào bucket, sort từng bucket. Tốt cho uniform float distribution. Worst case O(n squared) khi data skewed.
• Java Arrays.sort(int[]) dùng Dual-Pivot Quick, không Radix — vì không biết trước range. Muốn Radix sort thì dùng fastutil hoặc tự implement.
• Trade-off cốt lõi: non-comparison sort nhanh hơn nhưng tốn thêm O(n + k) space và yêu cầu biết trước key structure. Không có "free lunch" — chỉ là shift assumption từ "không biết gì về data" sang "biết range/digit/distribution".

12. Tự kiểm tra

Bài tiếp theo: Skip list — probabilistic balanced, code đơn giản hơn RBTree