Sắp xếp & tìm kiếm

Ở bài Độ phức tạp (Big-O), mèo con thấy tìm nhị phân nhanh hơn tìm tuyến tính cả trăm lần - nhưng có một điều kiện: dãy phải được sắp xếp trước. Sắp xếp là bước chuẩn bị đứng sau vô số việc: tìm nhanh, hiển thị có thứ tự, gộp dữ liệu, phát hiện trùng lặp.

Vấn đề là: sắp xếp cũng tốn chi phí, và cách sắp khác nhau thì đắt rẻ khác nhau rất xa. Bài này gặp bốn thuật toán kinh điển, chia làm hai nhóm: nhóm ngây thơ O(n²) và nhóm chia để trị O(n log n).

• ▸Sắp xếp là bước chuẩn bị cho tìm kiếm nhanh và nhiều việc khác.
• ▸Sắp một lần O(n log n), sau đó tìm nhị phân O(log n) cho mỗi truy vấn.
• ▸Các thuật toán sắp xếp khác nhau ở chi phí: O(n²) so với O(n log n).

Sắp xếp nổi bọt (bubble sort): đi từ trái sang phải, gặp cặp kề nhau nào sai thứ tự thì đổi chỗ; lặp đi lặp lại tới khi không còn cặp nào sai. Phần tử lớn cứ thế “nổi” dần về cuối như bọt khí.

function noiBot(a: number[]): number[] {
  const arr = [...a];
  for (let i = 0; i < arr.length - 1; i++)
    for (let j = 0; j < arr.length - 1 - i; j++)
      if (arr[j] > arr[j + 1]) [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
  return arr;
}

console.log(noiBot([5, 2, 8, 1, 9]));

[ 1, 2, 5, 8, 9 ]

Hai vòng lặp lồng nhau cho ta ngay O(n²) (đúng kiểu đã học ở bài Big-O). Sắp xếp chèn (insertion sort) cũng O(n²) nhưng có điểm hay: trên dãy gần như đã sắp, nó chỉ tốn gần O(n) vì hầu như không phải dời gì.

• ▸Nổi bọt: đổi chỗ cặp kề sai thứ tự, lặp tới khi xuôi - O(n²).
• ▸Chèn: lấy từng phần tử, chèn vào đúng chỗ trong phần đã sắp ở bên trái.
• ▸Cả hai O(n²), nhưng chèn rất nhanh khi dữ liệu gần như đã sắp (gần O(n)).

Muốn vượt rào O(n²), ta dùng chiến lược chia để trị (divide and conquer): chẻ bài toán thành các phần nhỏ, giải rồi ghép lại. Sắp xếp trộn (merge sort) chia đôi dãy tới khi mỗi phần chỉ còn một phần tử (hiển nhiên đã sắp), rồi trộn từng cặp lại theo thứ tự:

function tron(a: number[]): number[] {
  if (a.length <= 1) return a;            // mot phan tu thi da sap
  const mid = a.length >> 1;
  const trai = tron(a.slice(0, mid));      // sap nua trai
  const phai = tron(a.slice(mid));         // sap nua phai
  const out: number[] = [];
  let i = 0, j = 0;
  while (i < trai.length && j < phai.length) // tron hai nua da sap
    out.push(trai[i] <= phai[j] ? trai[i++] : phai[j++]);
  return [...out, ...trai.slice(i), ...phai.slice(j)];
}

console.log(tron([5, 2, 8, 1, 9, 3]));

[ 1, 2, 3, 5, 8, 9 ]

Chia đôi log n lần, mỗi tầng trộn tốn n - thành O(n log n). Sắp xếp nhanh (quicksort) cũng chia để trị: chọn một chốt (pivot), dồn số nhỏ hơn sang trái, lớn hơn sang phải, rồi đệ quy hai bên - trung bình cũng O(n log n).

Chọn một thuật toán, bấm Tiếp → hoặc Tự chạy và để ý ô Phép so sánh. Cùng một dãy, nhóm O(n²) và nhóm O(n log n) chênh nhau thấy rõ - và càng giãn khi bạn bấm Trộn lại với dãy khó hơn:

• ▸Nổi bọt luôn tốn n(n-1)/2 phép so sánh, bất kể dãy thế nào.
• ▸Trộn và nhanh tốn ít hơn hẳn khi dãy dài - đó là khác biệt O(n²) với O(n log n).
• ▸Chèn nhanh bất ngờ khi dãy đã gần sắp (ít phải dời).

Sắp xong rồi, tìm kiếm trở nên cực nhanh. Tìm nhị phân (binary search) nhìn phần tử ở giữa: nếu trúng thì xong; nếu mục tiêu nhỏ hơn thì chỉ tìm tiếp nửa trái, lớn hơn thì nửa phải. Mỗi bước bỏ đi một nửa, nên chỉ tốn O(log n):

function timNhiPhan(a: number[], x: number): number {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const giua = (lo + hi) >> 1;
    if (a[giua] === x) return giua;       // trung
    if (a[giua] < x) lo = giua + 1;       // tim nua phai
    else hi = giua - 1;                   // tim nua trai
  }
  return -1;                              // khong co
}

const daSap = [1, 3, 5, 7, 9, 11, 13];
console.log(timNhiPhan(daSap, 9));  // tim thay o chi so 4
console.log(timNhiPhan(daSap, 6));  // khong co

4
-1

• ▸Tìm nhị phân: O(log n), nhưng CHỈ chạy trên dãy đã sắp.
• ▸1 000 phần tử cần tối đa ~10 phép; 1 triệu phần tử ~20 phép.
• ▸Sắp một lần O(n log n), sau đó mỗi lần tìm chỉ O(log n) - rất đáng nếu tìm nhiều.

Mèo con giờ phân được hai “đẳng cấp” sắp xếp: ngây thơ O(n²) và chia để trị O(n log n), và biết vì sao phải sắp trước khi tìm nhị phân. Nhưng có một điều phiền: cứ thêm/xoá một phần tử là dãy lại lệch thứ tự, phải sắp lại.