Counting Sort TypeScript: Thuật toán sắp xếp O(n+k)

Bạn cần sắp xếp một triệu điểm thi, mỗi điểm nằm trong khoảng 0-100. Quick Sort hay Merge Sort sẽ mất O(n log n) vì chúng phải so sánh từng cặp phần tử. Nhưng nếu không so sánh mà chỉ đếm thì sao? Đó chính là ý tưởng của Counting Sort, với độ phức tạp O(n+k) - gần như tuyến tính khi phạm vi giá trị k đủ nhỏ.

Bài viết này sẽ hướng dẫn bạn cách Counting Sort hoạt động, cách implement bằng TypeScript, và quan trọng nhất: khi nào nó thắng thuật toán so sánh, khi nào nó là lựa chọn tệ.

1. Counting Sort là gì?

Counting Sort (thuật toán sắp xếp đếm) là thuật toán sắp xếp không dựa trên so sánh (non-comparison based sorting). Thay vì hỏi “phần tử A có lớn hơn B không?”, nó đếm xem mỗi giá trị xuất hiện bao nhiêu lần, rồi dựa vào bảng đếm đó để suy ra vị trí chính xác của từng phần tử trong mảng kết quả.

1.1. Đặc điểm chính

Không so sánh: Vị trí phần tử được tính ra từ tần suất, không phải từ phép so sánh
Chỉ dùng cho khóa nguyên: Giá trị phải là số nguyên (hoặc ánh xạ được về số nguyên) trong một phạm vi biết trước
Sắp xếp ổn định (stable): Giữ nguyên thứ tự tương đối của các phần tử bằng nhau - nhưng chỉ khi cài đặt đúng (xem mục duyệt ngược ở phần 2)
Phụ thuộc phạm vi k: O(n+k) chỉ nhanh khi k không quá lớn so với n; nếu k rất lớn, Counting Sort còn chậm hơn O(n log n)
Sử dụng bộ nhớ phụ: Cần thêm O(n+k) không gian cho mảng đếm và mảng kết quả

2. Cách hoạt động của Counting Sort

Thuật toán chạy qua 4 bước. Ta sẽ bám theo cùng một mảng ví dụ [11, 13, 12, 11, 15, 12] từ đầu đến cuối để bạn thấy dữ liệu biến đổi ra sao.

View Mermaid diagram code

flowchart TD
    Start([Mảng đầu vào]) --> MinMax["1. Tìm min và max<br/>→ biết phạm vi k"]
    MinMax --> Count["2. Đếm tần suất<br/>→ countArray"]
    Count --> Prefix["3. Cộng dồn tích lũy<br/>→ countArray thành vị trí"]
    Prefix --> Build["4. Duyệt ngược, rải vào output"]
    Build --> End([Mảng đã sắp xếp])

2.1. Tìm giá trị min và max

Trước tiên phải biết phạm vi giá trị, vì nó quyết định mảng đếm cần lớn bao nhiêu ô.

const numbers = [11, 13, 12, 11, 15, 12];

let min = numbers[0];
let max = numbers[0];

for (let i = 1; i < numbers.length; i++) {
  min = numbers[i] < min ? numbers[i] : min;
  max = numbers[i] > max ? numbers[i] : max;
}
// min = 11, max = 15

Giải thích:

Chỉ cần duyệt mảng đúng một lần: O(n)
Nhiều bài viết giả định mảng bắt đầu từ 0 và bỏ qua min. Giữ lại min giúp thuật toán chạy đúng với số âm, và tiết kiệm bộ nhớ khi giá trị nằm lệch xa 0 (ví dụ điểm số từ 900 đến 1000 chỉ cần 101 ô thay vì 1001 ô)

2.2. Tạo mảng đếm và tính tần suất

const range = max - min + 1; // chính là k trong O(n + k)
const countArray = new Array<number>(range).fill(0);

for (const num of numbers) {
  countArray[num - min] += 1;
}
// countArray = [2, 2, 1, 0, 1]
// tương ứng:    11 12 13 14 15

Giải thích:

Kích thước mảng đếm là max - min + 1 (tính cả hai đầu min và max)
Phép num - min dịch giá trị về index bắt đầu từ 0, nên countArray[i] là số lần xuất hiện của giá trị i + min
Giá trị 14 không có trong mảng nên ô của nó bằng 0 - những ô rỗng như vậy chính là cái giá bạn trả khi k lớn

Lưu ý quan trọng

Nếu bỏ - min và dùng thẳng num làm index, code sẽ sai âm thầm khi mảng có số âm. JavaScript không hề báo lỗi với index âm: countArray[-5] là undefined, nên countArray[-5]++ tính ra NaN và gắn một property thường tên "-5" lên object mảng. Property đó không được length đếm và bị mọi vòng lặp mảng bỏ qua, nên các số âm lặng lẽ biến mất khỏi kết quả:

const negatives = [-5, -2, 0, 3];
const negMin = -5;
const negCount = new Array<number>(9).fill(0);

// ❌ SAI - không offset
negCount[negatives[0]]++; // Không lỗi, nhưng tạo property "-5" = NaN
console.log(negCount.length); // 9 - property "-5" không được tính vào đây

// ✅ ĐÚNG - offset bởi min
negCount[negatives[0] - negMin]++; // Index: -5 - (-5) = 0

2.3. Tính tổng tích lũy

for (let i = 1; i < countArray.length; i++) {
  countArray[i] += countArray[i - 1];
}
// Trước: [2, 2, 1, 0, 1]
// Sau:   [2, 4, 5, 5, 6]

Giải thích:

Sau bước này, countArray[i] không còn là “số lần xuất hiện” nữa, mà là số phần tử có giá trị nhỏ hơn hoặc bằng i + min. Đọc mảng trên: có 2 phần tử ≤ 11, có 4 phần tử ≤ 12, có 5 phần tử ≤ 13…
Đây là mấu chốt của thuật toán: nếu có đúng 4 phần tử ≤ 12, thì phần tử 12 cuối cùng phải nằm ở vị trí thứ 4 trong mảng kết quả, tức index 3. Bảng đếm vừa biến thành bảng tra vị trí

2.4. Xây dựng mảng kết quả

const output = new Array<number>(numbers.length).fill(0);

for (let i = numbers.length - 1; i >= 0; i--) {
  const countIndex = numbers[i] - min;
  const outputIndex = countArray[countIndex] - 1; // trừ 1 vì index bắt đầu từ 0
  output[outputIndex] = numbers[i];
  countArray[countIndex] -= 1; // phần tử trùng giá trị tiếp theo lùi về ô trước
}
// output = [11, 11, 12, 12, 13, 15]

Giải thích: Lần lặp đầu tiên lấy phần tử cuối numbers[5] = 12. Tra countArray[12 - 11] = 4, vậy nó được đặt vào output[3]. Ô đếm giảm còn 3, nên số 12 tiếp theo (phần tử numbers[2]) sẽ rơi vào output[2] - ngay trước nó.

Tại sao phải duyệt ngược? Vì ta rải phần tử từ vị trí cuối của mỗi nhóm giá trị lùi dần về trước. Duyệt xuôi thì phần tử xuất hiện sớm trong input lại bị đặt vào ô sau, làm hai số 12 đảo chỗ cho nhau - thuật toán mất tính stable. Với mảng số thuần thì bạn không thấy khác biệt (12 nào cũng như nhau), nhưng khi sắp xếp object theo khóa số - ví dụ sắp danh sách sinh viên theo điểm - thứ tự ban đầu của những người bằng điểm sẽ bị xáo trộn. Phần 6.1 sẽ dùng đúng tính chất này.

3. Implementation đầy đủ trong TypeScript

function countingSort(numbers: number[]): number[] {
  // Xử lý trường hợp đặc biệt
  if (numbers.length <= 1) {
    return [...numbers];
  }

  const n = numbers.length;

  // Bước 1: Tìm min, max
  let min = numbers[0];
  let max = numbers[0];

  for (let i = 1; i < n; i++) {
    min = numbers[i] < min ? numbers[i] : min;
    max = numbers[i] > max ? numbers[i] : max;
  }

  // Bước 2: Tạo mảng đếm và tính tần suất
  const range = max - min + 1;
  const countArray = new Array<number>(range).fill(0);

  for (const num of numbers) {
    countArray[num - min] += 1;
  }

  // Bước 3: Tính tổng tích lũy
  for (let i = 1; i < countArray.length; i++) {
    countArray[i] += countArray[i - 1];
  }

  // Bước 4: Xây dựng mảng kết quả (duyệt ngược để giữ stable)
  const output = new Array<number>(n).fill(0);
  for (let i = n - 1; i >= 0; i--) {
    const countIndex = numbers[i] - min;
    const outputIndex = countArray[countIndex] - 1;
    output[outputIndex] = numbers[i];
    countArray[countIndex] -= 1;
  }

  return output;
}

// Sử dụng
const input = [11, 13, 12, 17, 11, 15, 12, 14, 11, 13];
console.log(countingSort(input));
// Output: [11, 11, 11, 12, 12, 13, 13, 14, 15, 17]

3.1. Ví dụ mở rộng với log chi tiết

function countingSortWithLog(numbers: number[]): number[] {
  console.log("Input:", numbers);

  const n = numbers.length;
  let min = numbers[0];
  let max = numbers[0];

  for (let i = 1; i < n; i++) {
    min = numbers[i] < min ? numbers[i] : min;
    max = numbers[i] > max ? numbers[i] : max;
  }

  const range = max - min + 1;
  console.log(`Min: ${min}, Max: ${max}, Range: ${range}`);

  const countArray = new Array<number>(range).fill(0);

  for (const num of numbers) {
    countArray[num - min] += 1;
  }

  console.log("Count array (frequency):", countArray);

  for (let i = 1; i < countArray.length; i++) {
    countArray[i] += countArray[i - 1];
  }

  console.log("Count array (cumulative):", countArray);

  const output = new Array<number>(n).fill(0);
  for (let i = n - 1; i >= 0; i--) {
    const countIndex = numbers[i] - min;
    const outputIndex = countArray[countIndex] - 1;
    output[outputIndex] = numbers[i];
    countArray[countIndex] -= 1;
  }

  console.log("Output:", output);
  return output;
}

// Test
countingSortWithLog([4, 2, 2, 8, 3, 3, 1]);

Kết quả:

Input: [4, 2, 2, 8, 3, 3, 1]
Min: 1, Max: 8, Range: 8
Count array (frequency): [1, 2, 2, 1, 0, 0, 0, 1]
Count array (cumulative): [1, 3, 5, 6, 6, 6, 6, 7]
Output: [1, 2, 2, 3, 3, 4, 8]

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

4.1. Time Complexity (Độ phức tạp thời gian)

Trường hợp	Độ phức tạp
Best case	O(n + k)
Average case	O(n + k)
Worst case	O(n + k)

Trong đó:

n: Số phần tử trong mảng
k: Phạm vi giá trị (max - min + 1)

Giải thích:

Tìm min/max: O(n)
Đếm tần suất: O(n)
Tính tổng tích lũy: O(k)
Xây dựng output: O(n)
Tổng: O(n + k)

4.2. Space Complexity (Độ phức tạp không gian)

O(n + k) - gồm mảng đếm O(k) và mảng kết quả O(n).

Lưu ý quan trọng

O(n + k) nghe có vẻ luôn thắng O(n log n), nhưng đó là vì ta hay quên rằng k có thể lớn tùy ý. Với [1, 1000000], ta có n = 2 và k = 999.999: thuật toán cấp phát một triệu ô nhớ, duyệt hết chúng ở bước cộng dồn, chỉ để sắp xếp đúng 2 số. Quick Sort xử lý xong trong vài phép so sánh.

Vì vậy trong production, hãy kiểm tra phạm vi trước rồi mới quyết định:

function smartSort(numbers: number[]): number[] {
  if (numbers.length <= 1) return [...numbers];

  const min = Math.min(...numbers);
  const max = Math.max(...numbers);
  const range = max - min + 1;

  // Heuristic: k lớn hơn n quá nhiều thì mảng đếm toàn ô rỗng
  if (range > numbers.length * 10) {
    // Fallback: Array.prototype.sort của V8 là TimSort - O(n log n) và stable
    return [...numbers].sort((a, b) => a - b);
  }

  return countingSort(numbers);
}

Hệ số 10 chỉ là điểm khởi đầu, không phải con số thiêng liêng - hãy đo trên dữ liệu thật của bạn. Điều quan trọng là có một ngưỡng, thay vì tin rằng O(n + k) luôn nhanh hơn.

5. So sánh với các thuật toán khác

Thuật toán	Time Complexity	Space	Stable	Khi nào dùng
Counting Sort	O(n + k)	O(n + k)	Yes	Khóa nguyên, k nhỏ
Quick Sort	O(n log n) tb, O(n²) xấu nhất	O(log n)	No	Đa dụng, sort tại chỗ
Merge Sort	O(n log n)	O(n)	Yes	Cần stable
`Array.sort()` (V8)	O(n log n)	O(n)	Yes	Mặc định nên dùng

Dòng cuối đáng chú ý: Array.prototype.sort trong V8 (Chrome, Node.js) dùng TimSort, đã stable theo chuẩn từ ES2019. Nghĩa là nếu bạn chỉ cần “sắp xếp và giữ stable”, bạn không cần tự viết Counting Sort - hàm có sẵn đã làm được. Counting Sort chỉ đáng công khi bạn thực sự khai thác được lợi thế O(n + k), tức là khi k nhỏ và n lớn.

Ưu điểm của Counting Sort:

Vượt qua giới hạn lý thuyết Ω(n log n) của sắp xếp so sánh, vì nó không so sánh
Stable, và là nền tảng cho Radix Sort (Radix gọi Counting Sort trên từng chữ số)
Chạy tuyến tính khi k = O(n)

Nhược điểm:

Chỉ dùng được với khóa nguyên trong phạm vi biết trước
Tốn O(k) bộ nhớ dù mảng chỉ có vài phần tử
Chậm hơn cả Array.sort() khi k lớn hơn n nhiều

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

6.1. Sắp xếp object theo khóa số

Đây là trường hợp Counting Sort thực sự tỏa sáng: sắp xếp object theo một khóa nguyên, và tính stable giữ nguyên thứ tự ban đầu của những người bằng điểm.

interface Student {
  name: string;
  score: number;
}

const MAX_SCORE = 100;

function sortStudentsByScore(students: Student[]): Student[] {
  if (students.length <= 1) return [...students];

  const countArray = new Array<number>(MAX_SCORE + 1).fill(0);

  for (const student of students) {
    const { score } = student;
    // Bắt buộc: điểm ngoài phạm vi sẽ làm hỏng mảng đếm một cách âm thầm
    if (!Number.isInteger(score) || score < 0 || score > MAX_SCORE) {
      throw new RangeError(`Điểm không hợp lệ: ${score} (${student.name})`);
    }
    countArray[score]++;
  }

  for (let i = 1; i < countArray.length; i++) {
    countArray[i] += countArray[i - 1];
  }

  const output = new Array<Student>(students.length);
  for (let i = students.length - 1; i >= 0; i--) {
    const { score } = students[i];
    countArray[score]--;
    output[countArray[score]] = students[i];
  }

  return output;
}

const students: Student[] = [
  { name: "An", score: 85 },
  { name: "Bình", score: 92 },
  { name: "Chi", score: 85 },
  { name: "Dũng", score: 78 },
];

console.log(sortStudentsByScore(students));
// [
//   { name: 'Dũng', score: 78 },
//   { name: 'An',   score: 85 },
//   { name: 'Chi',  score: 85 },  // An vẫn đứng trước Chi - stable
//   { name: 'Bình', score: 92 }
// ]

Giải thích:

Vòng kiểm tra Number.isInteger không phải cho có. Nếu một sinh viên có score: 105, countArray[105]++ sẽ tạo property rác thay vì báo lỗi, và sinh viên đó biến mất khỏi kết quả - đúng cái bẫy index đã nói ở phần 2.2. Điểm 85.5 cũng vậy
Kết quả giữ An trước Chi vì cả hai cùng 85 điểm và An đứng trước trong input. Đây là thứ Quick Sort không đảm bảo

6.2. Sắp xếp giá trị số thuần: bỏ luôn bước cộng dồn

Khi sắp xếp số thuần (không phải object), hai số 7 giống hệt nhau - không ai phân biệt được. Vậy nên bạn không cần mảng kết quả, cũng chẳng cần tổng tích lũy: cứ đếm rồi in lại theo thứ tự tăng dần.

const MAX_AGE = 120;

function sortAges(ages: number[]): number[] {
  const countArray = new Array<number>(MAX_AGE + 1).fill(0);

  for (const age of ages) {
    if (!Number.isInteger(age) || age < 0 || age > MAX_AGE) {
      throw new RangeError(`Tuổi không hợp lệ: ${age}`);
    }
    countArray[age]++;
  }

  const result: number[] = [];
  for (let age = 0; age <= MAX_AGE; age++) {
    for (let i = 0; i < countArray[age]; i++) {
      result.push(age);
    }
  }

  return result;
}

console.log(sortAges([25, 18, 30, 25, 22, 18, 35]));
// [18, 18, 22, 25, 25, 30, 35]

Giải thích:

Vòng lặp lồng nhau nhìn như O(n × k), nhưng vòng trong chỉ chạy tổng cộng đúng n lần (mỗi phần tử được push một lần), nên tổng vẫn là O(n + k)
Biến thể này vẫn O(n + k) thời gian nhưng chỉ tốn O(k) bộ nhớ phụ thay vì O(n + k) - dùng khi bạn sắp xếp số thuần và muốn tiết kiệm bộ nhớ

7. Khi nào nên và không nên dùng Counting Sort

7.1. Nên dùng khi:

✅ Khóa là số nguyên trong phạm vi nhỏ, biết trước - điểm thi (0-100), độ tuổi (0-120), kênh màu RGB (0-255), ngày trong tháng (1-31)

✅ n lớn hơn hẳn k - đây mới là lúc O(n + k) thực sự thắng O(n log n). Sắp xếp 1 triệu điểm thi trong khoảng 0-100 là ví dụ kinh điển

✅ Cần stable và tự cài đặt - ví dụ khi Counting Sort là bước con bên trong Radix Sort

// Hợp: n = 1.000.000, k = 101 → k << n
const scores = generateExamScores(1_000_000); // giá trị 0-100
countingSort(scores);

7.2. Không nên dùng khi:

❌ Phạm vi giá trị quá lớn - k lớn hơn n nhiều thì mảng đếm gần như toàn số 0

const ids = [1, 1_000_000]; // n = 2, k = 999.999
// Cấp phát 1 triệu ô để sắp 2 số → dùng Array.sort() thay thế

❌ Khóa không phải số nguyên và không ánh xạ được - chuỗi, số thực tùy ý. Nhưng chú ý: số thực có độ chính xác cố định thì vẫn map được

const prices = [19.99, 5.49, 19.99]; // ✅ nhân 100 → 1999, 549, 1999 (đơn vị xu)
const measurements = [3.14159, 2.71828]; // ❌ độ chính xác tùy ý, không map được

❌ Bộ nhớ hạn chế - Counting Sort luôn trả O(k) bộ nhớ, kể cả khi mảng chỉ có 3 phần tử

❌ Bạn chỉ cần “sắp xếp cho đúng” - Array.sort() đã stable và O(n log n). Đừng tự viết Counting Sort nếu không khai thác được lợi thế tuyến tính

Tóm lại, Counting Sort không phải là “thuật toán sắp xếp nhanh hơn Quick Sort” - nó là thuật toán đánh đổi bộ nhớ lấy tốc độ, và chỉ có lãi khi phạm vi giá trị k nhỏ so với số phần tử n. Trước khi dùng, hãy tự hỏi đúng một câu: k của mình bằng bao nhiêu so với n? Nếu k nhỏ và n lớn - điểm thi, độ tuổi, mã màu - bạn được sắp xếp tuyến tính gần như miễn phí. Nếu không, Array.sort() có sẵn vẫn là lựa chọn tốt hơn. Và nếu bạn muốn đi xa hơn, hãy tìm hiểu Radix Sort: nó lấy chính Counting Sort làm bước con để sắp xếp cả những số nguyên có phạm vi rất lớn.