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

Làm sao để sắp xếp một mảng số nguyên cực nhanh mà không cần so sánh từng phần tử? Counting Sort chính là câu trả lời! Khác với Quick Sort hay Merge Sort, Counting Sort đếm tần suất xuất hiện của từng phần tử và đạt độ phức tạp O(n+k) - nhanh hơn nhiều so với các thuật toán so sánh O(n log n).

Trong thực tế, Counting Sort được dùng rộng rãi để sắp xếp dữ liệu có phạm vi giá trị hạn chế: điểm thi (0-100), độ tuổi (0-120), mã màu RGB (0-255). Bài viết này sẽ hướng dẫn bạn cách hoạt động, implement trong TypeScript, và khi nào nên áp dụng thuật toán này.

#1. Counting Sort là gì?

Counting Sort (thuật toán sắp xếp đếm) là một thuật toán sắp xếp không dựa trên so sánh (non-comparison based sorting). Thay vì so sánh các phần tử với nhau, thuật toán này đếm số lần xuất hiện của mỗi giá trị và sử dụng thông tin đó để xác định vị trí chính xác của từng phần tử trong mảng đã sắp xếp.

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

  • Không so sánh: Không cần so sánh giá trị giữa các phần tử
  • Sắp xếp ổn định (stable): Giữ nguyên thứ tự tương đối của các phần tử có giá trị bằng nhau
  • Hiệu quả với phạm vi nhỏ: Hoạt động tốt nhất khi phạm vi giá trị (k) không quá lớn so với số phần tử (n)
  • Sử dụng bộ nhớ phụ: Cần thêm không gian để lưu mảng đếm

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

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

Đầu tiên, ta cần xác định phạm vi giá trị của mảng để biết kích thước mảng đếm cần tạo.

1
2
3
4
5
6
7
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;
}

Giải thích:

  • Duyệt qua mảng một lần để tìm giá trị nhỏ nhất và lớn nhất
  • Độ phức tạp: O(n)

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

1
2
3
4
5
6
const countArrSize = max - min + 1;
const countArray = Array.from<number>({ length: countArrSize }).fill(0);

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

Giải thích:

  • Kích thước mảng đếm = max - min + 1 (bao gồm cả min và max)
  • Sử dụng num - min làm index để xử lý trường hợp mảng không bắt đầu từ 0
  • countArray[i] lưu số lần xuất hiện của giá trị i + min

#Lưu ý quan trọng

Nếu không dùng num - min mà chỉ dùng num làm index, code sẽ lỗi khi mảng chứa số âm:

1
2
3
4
5
6
// ❌ SAI - không xử lý số âm
const arr = [-5, -2, 0, 3];
countArray[arr[0]]++; // Lỗi: index -5 không hợp lệ

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

Ví dụ:

1
2
3
4
// Input: [11, 13, 12, 11, 15, 12]
// min = 11, max = 15
// countArray = [2, 2, 1, 0, 1]
// Giải thích: 11 xuất hiện 2 lần, 12 xuất hiện 2 lần, 13 xuất hiện 1 lần, 14 xuất hiện 0 lần, 15 xuất hiện 1 lần

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

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

Giải thích:

  • Mỗi phần tử trong countArray bây giờ chứa số lượng phần tử nhỏ hơn hoặc bằng giá trị tương ứng
  • Giá trị này cho biết vị trí cuối cùng của phần tử trong mảng đã sắp xếp

Ví dụ tiếp theo:

1
2
3
// Sau bước 2: countArray = [2, 2, 1, 0, 1]
// Sau bước 3: countArray = [2, 4, 5, 5, 6]
// Ý nghĩa: có 2 phần tử ≤ 11, có 4 phần tử ≤ 12, có 5 phần tử ≤ 13, v.v.

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

1
2
3
4
5
6
7
const output = Array.from<number>({ length: n }).fill(0);
for (let i = n - 1; i >= 0; i--) {
  let countArrayIndex = numbers[i] - min;
  let outputArrayIndex = countArray[countArrayIndex] - 1;
  output[outputArrayIndex] = numbers[i];
  countArray[countArrayIndex] -= 1;
}

Giải thích:

  • Duyệt từ cuối về đầu để đảm bảo tính ổn định (stable)
  • Với mỗi phần tử numbers[i]:
    • Tìm vị trí trong countArray: numbers[i] - min
    • Lấy vị trí đặt phần tử: countArray[countArrayIndex] - 1 (trừ 1 vì index bắt đầu từ 0)
    • Đặt phần tử vào output
    • Giảm countArray đi 1 (để phần tử trùng giá trị tiếp theo được đặt ở vị trí trước đó)

Tại sao phải duyệt ngược? Nếu duyệt từ đầu về cuối, thứ tự các phần tử trùng giá trị sẽ bị đảo ngược, làm mất tính stable của thuật toán.

#3. Implementation đầy đủ trong TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
function countingSort(numbers: number[]): number[] {
  // Xử lý trường hợp đặc biệt
  if (numbers.length <= 1) {
    return numbers;
  }

  // Bước 1: Tìm min, max
  let 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;
  }

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

  for (let 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ả
  const output = Array.from<number>({ length: n }).fill(0);
  for (let i = n - 1; i >= 0; i--) {
    let countArrayIndex = numbers[i] - min;
    let outputArrayIndex = countArray[countArrayIndex] - 1;
    output[outputArrayIndex] = numbers[i];
    countArray[countArrayIndex] -= 1;
  }

  return output;
}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function countingSortWithLog(numbers: number[]): number[] {
  console.log("Input:", numbers);

  let 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;
  }

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

  const countArrSize = max - min + 1;
  const countArray = Array.from<number>({ length: countArrSize }).fill(0);

  for (let 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 = Array.from<number>({ length: n }).fill(0);
  for (let i = n - 1; i >= 0; i--) {
    let countArrayIndex = numbers[i] - min;
    let outputArrayIndex = countArray[countArrayIndex] - 1;
    output[outputArrayIndex] = numbers[i];
    countArray[countArrayIndex] -= 1;
  }

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

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

Kết quả:

1
2
3
4
5
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 caseO(n + k)
Average caseO(n + k)
Worst caseO(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) - cần:

  • Mảng đếm: O(k)
  • Mảng kết quả: O(n)

#Lưu ý quan trọng

Khi k >> n (phạm vi giá trị lớn hơn nhiều so với số phần tử), Counting Sort trở nên không hiệu quả:

1
2
3
4
5
6
7
8
9
10
// ❌ Không nên dùng Counting Sort
const arr = [1, 1000000]; // n = 2, k = 999999
// Mảng đếm cần 1 triệu phần tử cho chỉ 2 giá trị!

// ✅ Nên kiểm tra range trước khi dùng
const range = max - min + 1;
if (range > arr.length * 10) {
  // Fallback sang Quick Sort hoặc Merge Sort
  return arr.sort((a, b) => a - b);
}

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

Thuật toánTime ComplexitySpaceStableKhi nào dùng
Counting SortO(n + k)O(n + k)Yesk nhỏ, số nguyên
Quick SortO(n log n)O(log n)NoĐa dụng
Merge SortO(n log n)O(n)YesCần stable sort
Bubble SortO(n²)O(1)YesMảng nhỏ/học tập

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

  • Nhanh hơn các thuật toán so sánh khi k không quá lớn
  • Stable - giữ nguyên thứ tự tương đối
  • Dễ hiểu và implement

Nhược điểm:

  • Chỉ hoạt động với số nguyên hoặc có thể map về số nguyên
  • Tốn bộ nhớ khi phạm vi giá trị lớn
  • Không hiệu quả khi k >> n

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

#6.1. Sắp xếp điểm số

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
interface Student {
  name: string;
  score: number;
}

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

  // Giả sử điểm từ 0-100
  const countArray = new Array(101).fill(0);

  // Đếm số học sinh mỗi điểm
  for (let student of students) {
    countArray[student.score]++;
  }

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

  // Xây dựng kết quả
  const output: Student[] = new Array(students.length);
  for (let i = students.length - 1; i >= 0; i--) {
    const score = students[i].score;
    const position = countArray[score] - 1;
    output[position] = students[i];
    countArray[score]--;
  }

  return output;
}

// Test
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));
// Output: [
//   { name: 'Dũng', score: 78 },
//   { name: 'An', score: 85 },
//   { name: 'Chi', score: 85 },  // Giữ nguyên thứ tự An trước Chi
//   { name: 'Bình', score: 92 }
// ]

#6.2. Sắp xếp độ tuổi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function sortByAge(ages: number[]): number[] {
  // Giả sử độ tuổi từ 0-120
  const countArray = new Array(121).fill(0);

  for (let age of ages) {
    countArray[age]++;
  }

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

  return result;
}

console.log(sortByAge([25, 18, 30, 25, 22, 18, 35]));
// Output: [18, 18, 22, 25, 25, 30, 35]

Giải thích:

  • Phương pháp đơn giản hơn khi không cần giữ stable
  • Chỉ cần đếm tần suất rồi rebuild mảng theo thứ tự

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

#7.1. Nên dùng khi:

✅ Phạm vi giá trị nhỏ và biết trước

1
2
3
4
5
6
7
8
// Điểm số 0-100
sortExamScores([85, 92, 78, 85, 95]);

// Độ tuổi 0-120
sortAges([25, 18, 30, 22, 35]);

// Mã màu RGB 0-255
sortColorValues([128, 255, 64, 0, 128]);

✅ Cần sắp xếp stable - giữ nguyên thứ tự tương đối của các phần tử trùng giá trị

✅ Dataset lớn với range nhỏ - k ≈ n hoặc k << n

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

❌ Phạm vi giá trị quá lớn

1
2
const arr = [1, 1000000]; // Range = 999,999 cho 2 phần tử
// Tốn 1 triệu ô nhớ → dùng Quick Sort thay thế

❌ Dữ liệu không phải số nguyên (hoặc không map được về số nguyên)

1
2
const floats = [3.14, 2.71, 1.41]; // Counting Sort không áp dụng
const strings = ["apple", "banana"]; // Cần thuật toán khác

❌ Bộ nhớ hạn chế - Counting Sort cần O(n + k) bộ nhớ phụ

Vậy là bạn đã nắm vững Counting Sort - từ cách hoạt động, implementation cho đến khi nào nên áp dụng. Với độ phức tạp O(n + k), Counting Sort vượt trội các thuật toán so sánh O(n log n) khi điều kiện phù hợp. Trong thực tế, hãy kiểm tra phạm vi giá trị trước khi quyết định dùng Counting Sort, và cân nhắc fallback sang Quick Sort hoặc Merge Sort nếu range quá lớn. Hãy thử áp dụng vào dự án của bạn - sắp xếp điểm thi, xếp hạng người dùng theo tuổi, hay bất kỳ dataset nào có phạm vi giá trị hạn chế!



Tags

Related posts