Sorting
Algorithms

7.1 Tiêu chí so sánh thuật toán sort

5 tiêu chí cần nhớ:

Time complexity

• Best case: input "tốt" nhất (vd đã sort sẵn)
• Average case: input ngẫu nhiên
• Worst case: input "xấu" nhất (vd sort ngược)

Space complexity

Bộ nhớ thêm cần (không tính input). In-place = O(1) hoặc O(log n) extra space.

Stable

Stable = giữ nguyên thứ tự tương đối của các phần tử bằng nhau. Quan trọng khi sort theo nhiều criteria.

// Vd: sort users theo age, giữ thứ tự xuất hiện ban đầu khi cùng age
const users = [
  {name: "A", age: 30},
  {name: "B", age: 25},
  {name: "C", age: 30},  // cùng age với A
];
// Stable sort: A trước C (giữ nguyên thứ tự ban đầu)
// Unstable sort: có thể C trước A

Comparison-based hay không

Sort dựa trên so sánh (vd a < b) không thể nhanh hơn O(n log n) trên worst case (giới hạn lý thuyết). Sort không so sánh (Counting, Radix) có thể đạt O(n) nhưng chỉ với input đặc biệt.

Adaptive

Adaptive sort chạy nhanh hơn trên input "gần sort" (Insertion, TimSort).

7.2 Bubble Sort — O(n²)

Ý tưởng: đi qua mảng, swap các cặp kề nhau nếu sai thứ tự. Lặp lại đến khi không còn swap. Phần tử lớn nhất "nổi lên" cuối mảng như bong bóng → tên "bubble".

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break;  // optimization: đã sort
  }
  return arr;
}

• Time: O(n²) avg/worst, O(n) best (đã sort)
• Space: O(1) — in-place
• Stable: ✓ (chỉ swap khi >, không swap khi bằng)

Bubble sort là sort chậm nhất trong các sort O(n²). Chỉ tốt để dạy học.

7.3 Selection Sort — O(n²)

Ý tưởng: mỗi vòng, tìm phần tử nhỏ nhất trong phần chưa sort, swap về đầu.

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) minIdx = j;
    }
    if (minIdx !== i) [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
  }
  return arr;
}

• Time: O(n²) trong mọi trường hợp
• Space: O(1)
• Stable: ✗ (swap có thể đảo thứ tự phần tử bằng)
• Đặc điểm: ÍT swap nhất (n-1 swap) — tốt khi swap đắt

7.4 Insertion Sort — O(n²) worst, O(n) best

Ý tưởng: như sắp bài trên tay — lấy từng lá, chèn vào vị trí đúng trong phần đã sort.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    // Dịch các phần tử lớn hơn key về phía sau
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;  // chèn vào vị trí đúng
  }
  return arr;
}

• Time: O(n²) avg/worst, O(n) best (đã sort)
• Space: O(1)
• Stable: ✓
• Adaptive: ✓ — nhanh trên input "gần sort"

7.5 Merge Sort — O(n log n) đảm bảo

Divide & Conquer: (1) Chia mảng đôi đệ quy đến khi rỗng/1 phần tử, (2) Merge 2 mảng đã sort thành 1 mảng sort.

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) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else                     result.push(right[j++]);
  }
  while (i < left.length)  result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);
  return result;
}

Recurrence relation

T(n) = 2T(n/2) + O(n) → Master theorem case 2 → O(n log n).

• Time: O(n log n) trong mọi trường hợp (best/avg/worst)
• Space: O(n) — không in-place
• Stable: ✓ (khi <= thay vì < trong merge)

Khi nào dùng?

• Sort linked list (đã thấy ở Chương 3)
• External sort (sort file lớn không vừa RAM)
• Khi cần stable sort guaranteed O(n log n)

7.6 Quick Sort — O(n log n) avg, O(n²) worst

Divide & Conquer với pivot: (1) Chọn pivot, (2) Partition: phần tử nhỏ hơn pivot sang trái, lớn hơn sang phải, (3) Đệ quy sort 2 phần.

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo < hi) {
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
  }
  return arr;
}

// Lomuto partition (đơn giản hơn Hoare)
function partition(arr, lo, hi) {
  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]];
    }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}

Vấn đề: Worst case O(n²)

Khi pivot là min/max của mảng (vd: pivot luôn là phần tử cuối + mảng đã sort), partition không đều → O(n²). Khắc phục:

• Random pivot: chọn pivot ngẫu nhiên → tránh worst case "có chủ đích"
• Median-of-three: pick median của arr[lo], arr[mid], arr[hi]
• Introsort: chuyển sang Heap Sort khi đệ quy sâu quá 2 log n

// Quick Sort với random pivot
function partitionRandom(arr, lo, hi) {
  const pivotIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[pivotIdx], arr[hi]] = [arr[hi], arr[pivotIdx]];
  return partition(arr, lo, hi);
}

• Time: O(n log n) avg, O(n²) worst
• Space: O(log n) cho call stack (in-place partition)
• Stable: ✗ (partition có thể đảo thứ tự)

Tại sao Quick Sort thực tế nhanh hơn Merge Sort?

• Cache friendly hơn (in-place, ít cấp phát memory)
• Constant factor thấp hơn
• Trung bình rất ổn định, worst case hiếm gặp khi có random pivot

Quickselect — biến thể tìm phần tử thứ k

// Tìm phần tử thứ k smallest mà KHÔNG cần sort hết
// Time: O(n) trung bình, O(n²) worst
function quickselect(arr, k, lo = 0, hi = arr.length - 1) {
  if (lo === hi) return arr[lo];
  const p = partition(arr, lo, hi);
  if (p === k) return arr[k];
  if (k < p) return quickselect(arr, k, lo, p - 1);
  return quickselect(arr, k, p + 1, hi);
}

// Bài LeetCode "Kth Largest Element" giải bằng quickselect

7.7 Heap Sort — O(n log n) đảm bảo, in-place

Ý tưởng: build max-heap từ mảng, lấy max liên tục đặt về cuối. Heap sẽ học chi tiết ở Chương 10.

function heapSort(arr) {
  const n = arr.length;

  // Build max-heap (heapify từ cuối lên)
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(arr, n, i);
  }

  // Lấy max ra cuối, giảm size, heapify lại
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    siftDown(arr, i, 0);
  }
  return arr;
}

function siftDown(arr, n, i) {
  while (true) {
    let largest = i;
    const l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest === i) break;
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    i = largest;
  }
}

• Time: O(n log n) đảm bảo (best/avg/worst)
• Space: O(1) in-place
• Stable: ✗

Heap Sort có Big-O đảm bảo và in-place — hơn Quick Sort về worst case, hơn Merge Sort về memory. Nhưng constant factor lớn hơn.

7.8 Counting Sort — O(n+k) không so sánh

Ý tưởng: đếm tần suất xuất hiện của mỗi giá trị, dựng output từ count. Chỉ áp dụng được khi giá trị là số nguyên trong khoảng nhỏ.

function countingSort(arr) {
  if (arr.length === 0) return arr;
  const max = Math.max(...arr);
  const min = Math.min(...arr);
  const count = new Array(max - min + 1).fill(0);

  // Đếm tần suất
  for (const x of arr) count[x - min]++;

  // Dựng output
  let idx = 0;
  for (let i = 0; i < count.length; i++) {
    while (count[i]-- > 0) arr[idx++] = i + min;
  }
  return arr;
}

• Time: O(n + k), k = max - min
• Space: O(k)
• Stable: ✓ (với cài đặt đầy đủ dùng prefix sum)
• Limitation: chỉ cho integer trong khoảng hẹp

Khi nào dùng? Sort điểm thi (0-100), tuổi (0-150), ký tự ASCII, dữ liệu có range giới hạn.

7.9 Radix Sort — sort theo từng "chữ số"

Ý tưởng: sort theo từng chữ số, từ ít quan trọng nhất (LSD) đến quan trọng nhất. Mỗi pass dùng Counting Sort.

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

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

  for (const x of arr) count[Math.floor(x / exp) % 10]++;
  // Prefix sum để giữ stable
  for (let i = 1; i < 10; i++) count[i] += count[i - 1];
  // Build output (duyệt ngược để stable)
  for (let i = n - 1; i >= 0; i--) {
    const d = Math.floor(arr[i] / exp) % 10;
    output[--count[d]] = arr[i];
  }
  for (let i = 0; i < n; i++) arr[i] = output[i];
}

• Time: O(d · (n + k)) với d = số digit, k = base (thường 10)
• Space: O(n + k)
• Stable: ✓

Radix Sort vượt qua giới hạn O(n log n) cho integer/string, là vũ khí cho big data sort.

7.10 TimSort — V8 và Python dùng

TimSort (Tim Peters, 2002) là hybrid Merge Sort + Insertion Sort. Đây là default sort của:

• JavaScript V8 (Node, Chrome) từ 2018
• Python từ 2.3
• Java cho Object array từ Java 7
• Android, Apple Swift

Nguyên lý

1. Phát hiện "runs" (đoạn đã tăng/giảm sẵn) trong mảng
2. Sort các run nhỏ bằng Insertion Sort (cực nhanh trên đoạn ngắn)
3. Merge các run với chiến lược thông minh (giữ stack run, merge khi vi phạm bất đẳng thức)

Tại sao TimSort xuất sắc?

• O(n) trên input đã sort hoặc gần sort (real-world data thường có pattern)
• O(n log n) đảm bảo worst case
• Stable
• Adaptive

Đó là lý do bạn không cần code sort thủ công — arr.sort() trong JS đã rất tốt (chỉ cần custom comparator nếu cần).

// arr.sort() mặc định convert sang string để so sánh — bug kinh điển
[10, 2, 1].sort();  // [1, 10, 2] (!)

// Phải truyền comparator cho number
[10, 2, 1].sort((a, b) => a - b);  // [1, 2, 10]

// Sort object theo property
users.sort((a, b) => a.age - b.age);
users.sort((a, b) => a.name.localeCompare(b.name));

7.11 Bảng tổng hợp — học thuộc

Cheat sheet "khi nào dùng cái gì"

Bài tập

[2,0,2,1,1,0] → [0,0,1,1,2,2]

→ [[1,6],[8,10],[15,18]]

[3,30,34,5,9] → "9534330"

Tổng kết chương 7

• ✅ Sort comparison-based ≥ O(n log n) (giới hạn lý thuyết)
• ✅ Bubble/Selection/Insertion = O(n²); Insertion adaptive O(n) trên gần sort
• ✅ Merge Sort = O(n log n) đảm bảo, stable, không in-place
• ✅ Quick Sort = O(n log n) avg, in-place; random pivot tránh worst case O(n²)
• ✅ Heap Sort = O(n log n) đảm bảo, in-place, không stable
• ✅ Counting/Radix Sort không so sánh, vượt O(n log n) cho integer/string
• ✅ TimSort = hybrid Merge + Insertion → V8/Python/Java dùng
• ✅ arr.sort() không truyền comparator → convert sang string. Luôn truyền (a,b)=>a-b cho number.
• ✅ Quickselect tìm phần tử thứ k trong O(n) — bài Kth Largest