Khi nào một lập trình viên cấp độ Junior nên lựa chọn thuật toán Counting Sort thay vì các thuật toán sắp xếp dựa trên so sánh như Quick Sort hay Merge Sort trong môi trường Enterprise?

Question

Accepted Answer

Bản chất cơ chế hoạt động
Counting Sort là thuật toán sắp xếp không dựa trên so sánh (non-comparison-based sorting). Thuật toán hoạt động bằng cách đếm số lần xuất hiện của mỗi giá trị phần tử duy nhất trong mảng đầu vào, sau đó tính toán vị trí của từng phần tử trong mảng kết quả.
Độ phức tạp

Độ phức tạp thời gian: O(n + k) với n là số lượng phần tử và k là giá trị lớn nhất trong mảng.
Độ phức tạp không gian: O(k) để lưu trữ mảng đếm.

Khi nào nên sử dụng

Khi miền giá trị k của dữ liệu đầu vào không quá lớn so với số lượng phần tử n.
Thường dùng trong các bài toán thực tế như sắp xếp điểm số của học sinh (từ 0 đến 10), sắp xếp độ tuổi, hoặc xử lý dữ liệu tần suất xuất hiện ký tự trong chuỗi.

Ví dụ minh họa code
function countingSort(arr) {
  if (arr.length === 0) return arr;
  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);

for (let num of arr) {
    count[num]++;
  }

const sortedArray = [];
  for (let i = 0; i <= max; i++) {
    while (count[i] > 0) {
      sortedArray.push(i);
      count[i]--;
    }
  }
  return sortedArray;
}
Lưu ý kinh nghiệm thực chiến
Không sử dụng Counting Sort khi miền giá trị k quá lớn (ví dụ sắp xếp các số định danh UUID hoặc số căn cước công dân) vì sẽ gây lãng phí bộ nhớ nghiêm trọng (Memory Leak hoặc Out of Memory), dẫn đến sập ứng dụng Backend.

Khi nào một lập trình viên cấp độ Junior nên lựa chọn thuật toán Counting Sort thay vì các thuật toán sắp xếp dựa trên so sánh như Quick Sort hay Merge Sort trong môi trường Enterprise?

Bản chất cơ chế hoạt động

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi sorting liên quan cùng chủ đề