Bài 3: Sorting Algorithms Visualizer — Quick, Merge, Heap, Radix Sort

Ở Bài 2 chúng ta đã so sánh Dijkstra và A* qua số node phải khám phá. Bài này áp dụng đúng tư duy đó cho một bài toán quen thuộc hơn nhiều: sắp xếp mảng — nhưng lần này đua trực tiếp 4 giải thuật sắp xếp kinh điển cạnh nhau để xem thuật toán nào thực sự nhanh hơn, và tại sao.

1. Vì sao có nhiều giải thuật sắp xếp đến vậy?

Không có một giải thuật sắp xếp nào "tốt nhất tuyệt đối" — mỗi giải thuật đánh đổi giữa độ phức tạp thời gian, bộ nhớ phụ trợ, và tính ổn định (stability — giữ nguyên thứ tự tương đối của các phần tử bằng nhau). Phần lớn giải thuật sắp xếp dựa trên so sánh (comparison-based) đều bị chặn dưới ở $\Omega(n \log n)$ trong trường hợp trung bình — không thể nhanh hơn về mặt lý thuyết. Nhưng vẫn có ngoại lệ, như Radix Sort ở phần 4.

2. Quick Sort: Chia để trị bằng Pivot

Quick Sort (Tony Hoare, 1959) chọn một phần tử làm pivot, chia mảng thành 2 phần — nhỏ hơn pivot và lớn hơn pivot — rồi đệ quy sắp xếp từng phần. Với sơ đồ phân hoạch Lomuto dưới đây, pivot luôn là phần tử cuối cùng:

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return;
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]]; // hoán đổi
    }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]]; // đặt pivot vào đúng vị trí
  quickSort(arr, lo, i);      // đệ quy nửa nhỏ hơn pivot
  quickSort(arr, i + 2, hi);  // đệ quy nửa lớn hơn pivot
}

Trung bình Quick Sort đạt $O(n \log n)$ và thường nhanh nhất trong thực tế nhờ locality bộ nhớ tốt (in-place, ít cấp phát mảng phụ). Nhưng nó không ổn định và có trường hợp xấu nhất $O(n^2)$.

3. Merge Sort: Ổn định nhờ chia đôi đệ quy

Merge Sort (John von Neumann, 1945) chia mảng làm đôi liên tục tới khi còn 1 phần tử, rồi hợp nhất (merge) từng cặp mảng con đã sắp lại với nhau. Vì luôn ưu tiên lấy phần tử từ mảng trái khi bằng nhau, Merge Sort ổn định tuyệt đối:

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    // "<=" (không phải "<") giữ ổn định: ưu tiên bên trái khi bằng nhau
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return result.concat(left.slice(i), right.slice(j));
}

Merge Sort luôn đạt $O(n \log n)$ ở mọi trường hợp (không có worst case tệ như Quick Sort), nhưng cần thêm bộ nhớ phụ $O(n)$ vì không sắp xếp tại chỗ (in-place).

4. Heap Sort: Sắp xếp tại chỗ bằng Binary Heap

Heap Sort xây một max-heap từ mảng (phần tử lớn nhất luôn ở gốc), rồi liên tục lấy gốc ra và đưa xuống cuối mảng, "heapify" lại phần còn lại. Đây là cách kết hợp ưu điểm $O(n \log n)$ đảm bảo của Merge Sort với bộ nhớ $O(1)$ tại chỗ của Quick Sort:

function heapSort(arr) {
  const n = arr.length;
  // Bước 1: Xây max-heap từ dưới lên
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(arr, n, i);

  // Bước 2: Lấy gốc (max) ra cuối, thu nhỏ heap, heapify lại
  for (let end = n - 1; end > 0; end--) {
    [arr[0], arr[end]] = [arr[end], arr[0]];
    heapify(arr, end, 0);
  }
}

function heapify(arr, size, root) {
  let largest = root;
  const left = 2 * root + 1, right = 2 * root + 2;
  if (left < size && arr[left] > arr[largest]) largest = left;
  if (right < size && arr[right] > arr[largest]) largest = right;
  if (largest !== root) {
    [arr[root], arr[largest]] = [arr[largest], arr[root]];
    heapify(arr, size, largest); // heapify tiếp xuống nhánh vừa đổi
  }
}

5. Radix Sort: Sắp xếp không so sánh theo từng chữ số

Radix Sort (LSD — Least Significant Digit) sắp xếp số nguyên bằng cách phân nhóm (bucket) lần lượt theo chữ số hàng đơn vị, hàng chục, hàng trăm... Mỗi lượt dùng counting sort ổn định để không phá vỡ thứ tự đã sắp ở các chữ số thấp hơn trước đó:

function radixSort(arr) {
  const max = Math.max(...arr);
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    countingSortByDigit(arr, exp);
  }
}

function countingSortByDigit(arr, exp) {
  const n = arr.length;
  const output = new Array(n);
  const count = new Array(10).fill(0);

  for (let i = 0; i < n; i++) count[Math.floor(arr[i] / exp) % 10]++;
  for (let i = 1; i < 10; i++) count[i] += count[i - 1]; // cộng dồn vị trí

  // Duyệt NGƯỢC để giữ ổn định (stable)
  for (let i = n - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    output[--count[digit]] = arr[i];
  }
  for (let i = 0; i < n; i++) arr[i] = output[i];
}

6. So sánh 4 giải thuật sắp xếp

Sân chơi tương tác: Sorting Race Visualizer

Bấm "Chạy đua" để xem cả 4 giải thuật sắp xếp cùng một mảng ngẫu nhiên song song — quan sát số phép so sánh/hoán đổi và xem thuật toán nào "về đích" trước.