Thuật toán 3 — Sắp xếp & tìm kiếm

Vì sao sắp xếp và tìm kiếm là "hai chân" của xử lý dữ liệu?

Gần như mọi báo cáo, mọi lần đối soát, mọi bảng xếp hạng khách hàng đều bắt đầu bằng một trong hai động tác: sắp xếp dữ liệu theo một tiêu chí, hoặc tìm kiếm một giá trị (hay một ngưỡng) trong dữ liệu. Hai việc này gắn chặt nhau: một khi dữ liệu đã được sắp, việc tìm kiếm rẻ đi từ O(n) xuống O(log n), và nhiều bài toán tưởng chừng đắt (đối soát hai danh sách, khử trùng, gộp) trở thành tuyến tính.

Bài này không dạy bạn tự cài lại quicksort để dùng trong production — Python đã có sorted(), list.sort() và module bisect viết bằng C, nhanh và đúng hơn hầu hết code tự viết. Mục tiêu là hiểu cái gì đang chạy bên dưới, chi phí bao nhiêu, và khi nào một cách làm ngây thơ O(n²) âm thầm giết chết job của bạn. Nếu bạn chưa chắc về ký hiệu Big-O, hãy đọc lại Độ phức tạp trước; nếu cần ôn list/dict/set thì xem Cấu trúc dữ liệu.

Toàn bộ code dưới đây là minh hoạ — danh mục Python, không chạy trên sandbox SQL của khoá.

1. Sắp xếp: từ ngây thơ đến thực chiến

Bubble/insertion sort — O(n²), chỉ để hiểu

Bubble sort và insertion sort là cách con người sắp bài trên tay: lấy từng phần tử, đẩy nó về đúng chỗ so với những phần tử đã xếp. Chúng dễ hiểu nhưng chi phí O(n²): với 10.000 dòng là ~100 triệu phép so sánh, với 1 triệu dòng thì thực tế không chạy nổi.

# insertion sort — (minh hoạ) chỉ để hiểu, đừng dùng trong production
def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:   # đẩy phần tử lớn hơn sang phải
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

Điểm hay duy nhất của insertion sort: với mảng gần như đã sắp, nó gần O(n). Ý tưởng này không bị vứt đi — Timsort của Python tận dụng đúng nó (xem phần 3).

Merge sort & quicksort — O(n log n)

Hai thuật toán "chia để trị" đưa chi phí xuống O(n log n):

• Merge sort: chia mảng làm đôi, sắp mỗi nửa (đệ quy), rồi trộn (merge) hai nửa đã sắp thành một. Trộn hai danh sách đã sắp chỉ tốn O(n) — đây là chìa khoá dùng lại ở phần đối soát. Merge sort ổn định (stable) và có worst-case đảm bảo O(n log n), nhưng tốn thêm O(n) bộ nhớ.
• Quicksort: chọn một "chốt" (pivot), phân hoạch mảng thành phần nhỏ hơn và phần lớn hơn chốt, rồi đệ quy. Trung bình O(n log n), sắp tại chỗ (in-place, ít tốn bộ nhớ), nhưng worst-case O(n²) nếu chọn chốt tồi (ví dụ mảng đã sắp sẵn với chốt là phần tử đầu). Quicksort không ổn định.

Sơ đồ trên là tinh thần merge sort: chia đến khi mỗi mảnh còn 1 phần tử (hiển nhiên đã sắp), rồi trộn ngược lên. Cây chia có chiều cao log n, mỗi tầng trộn tốn O(n) → tổng O(n log n).

Vì sao O(n log n) là giới hạn dưới của sắp xếp dựa so sánh?

Đây là một kết quả đẹp và cần nhớ: mọi thuật toán sắp xếp chỉ dựa vào so sánh hai phần tử (a < b?) không thể nhanh hơn Ω(n log n) trong trường hợp xấu nhất.

Trực giác chứng minh (cây quyết định): với n phần tử có n! cách hoán vị khả dĩ, và chỉ đúng một cách là thứ tự đã sắp. Mỗi phép so sánh cho ra một trong hai nhánh (đúng/sai), nên chuỗi so sánh tạo thành một cây nhị phân. Để phân biệt được cả n! kết quả, cây phải có ít nhất n! lá. Cây nhị phân cao h có tối đa 2^h lá, nên 2^h ≥ n!, suy ra h ≥ log₂(n!). Theo xấp xỉ Stirling, log₂(n!) ≈ n log₂ n − O(n) = Ω(n log n).

Ý nghĩa thực tế: đừng cố tìm thuật toán sắp xếp so sánh "nhanh hơn O(n log n)" — nó không tồn tại. Muốn nhanh hơn, bạn phải không dùng so sánh (phần 2).

Ổn định (stable) vs không ổn định — vì sao quan trọng khi sắp nhiều khoá

Một thuật toán stable giữ nguyên thứ tự tương đối của các phần tử bằng khoá. Điều này cực kỳ quan trọng khi bạn sắp theo nhiều tiêu chí bằng cách sắp nhiều lần:

Muốn sắp giao dịch theo (chi nhánh tăng dần, số tiền giảm dần), với thuật toán stable bạn có thể sắp theo số tiền trước, rồi sắp theo chi nhánh — lần sắp thứ hai không phá vỡ thứ tự số tiền trong cùng một chi nhánh.

Nếu thuật toán không ổn định, thủ thuật "sắp nhiều lần" này sai. May thay, Python luôn dùng sort ổn định.

2. Sắp xếp không dựa so sánh — O(n) khi miền giá trị hẹp

Giới hạn Ω(n log n) chỉ áp cho thuật toán so sánh. Nếu khoá có miền giá trị hẹp và biết trước, ta có thể sắp trong O(n) mà không so sánh cặp nào:

• Counting sort: đếm số lần xuất hiện của mỗi giá trị rồi ghi lại theo thứ tự. Hợp khi miền giá trị nhỏ so với n — ví dụ sắp theo trạng thái giao dịch (vài giá trị), tháng (1–12), điểm tín dụng (300–850).
• Radix sort: sắp theo từng chữ số/ký tự, từ thấp đến cao, dùng counting sort ổn định ở mỗi bước. Hợp cho khoá độ dài cố định như ngày YYYYMMDD, mã tài khoản, số CIF.
• Bucket sort: chia miền giá trị thành các "xô" đều nhau, sắp trong từng xô. Hợp khi dữ liệu phân bố tương đối đều.

Khi nào dùng? Khi miền giá trị hẹp và cố định. Với dữ liệu ngân hàng, radix sort trên ngày dạng số nguyên có thể nhanh hơn sort so sánh trên nhiều triệu bản ghi. Nhưng trong thực tế Python, phần lớn trường hợp sorted() với Timsort đã đủ nhanh — chỉ đổi khi đo được nút thắt thực sự.

3. Timsort — thuật toán sort thực chiến của Python

sorted() và list.sort() của Python (cũng như Arrays.sort cho object trong Java) dùng Timsort — thuật toán lai giữa merge sort và insertion sort, do Tim Peters thiết kế cho Python từ bản 2.3. Ba đặc điểm cần nhớ:

1. Ổn định (stable) — nên thủ thuật sắp nhiều khoá ở trên luôn đúng.
2. Worst-case O(n log n) đảm bảo — không rơi vào O(n²) như quicksort ngây thơ.
3. Thích nghi (adaptive) — nó dò các đoạn đã sắp sẵn ("run") trong dữ liệu thật và tận dụng chúng. Với dữ liệu gần như đã sắp (rất thường gặp: log theo thời gian, dữ liệu tăng dần), Timsort tiệm cận O(n).

Bên trong, Timsort dùng binary insertion sort cho các đoạn ngắn rồi trộn các run lại theo kiểu merge sort với bộ nhớ tiết kiệm. Kết luận thực dụng: dùng sorted(), đừng tự viết — bạn khó lòng đánh bại được Timsort về cả tốc độ lẫn độ đúng.

Sắp theo key và nhiều khoá

# Sắp giao dịch theo (chi nhánh tăng, số tiền giảm) — (minh hoạ)
txns = [
    {"branch": "HN", "amount": 5_000_000, "id": "T1"},
    {"branch": "HN", "amount": 8_000_000, "id": "T2"},
    {"branch": "HCM", "amount": 8_000_000, "id": "T3"},
    {"branch": "HN", "amount": 8_000_000, "id": "T4"},
]

# Cách 1: một key tuple. Dấu trừ để đảo chiều số tiền
ranked = sorted(txns, key=lambda t: (t["branch"], -t["amount"]))

# Cách 2: sắp nhiều lần, tận dụng tính ổn định (khi không đảo được bằng dấu trừ,
# ví dụ khoá là chuỗi thì dùng reverse=True cho lần sắp phụ)
tmp = sorted(txns, key=lambda t: t["amount"], reverse=True)  # khoá phụ trước
ranked2 = sorted(tmp, key=lambda t: t["branch"])             # khoá chính sau

Lưu ý: T2 và T4 cùng chi nhánh HN, cùng số tiền — vì Timsort ổn định, thứ tự gốc (T2 trước T4) được giữ nguyên. Đó là hành vi bạn muốn khi cần kết quả xác định, tái lập được (deterministic), điều rất quan trọng cho báo cáo và đối soát.

4. Tìm kiếm nhị phân — O(log n) trên dữ liệu đã sắp

Một khi dữ liệu đã sắp, tìm kiếm nhị phân (binary search) tìm được vị trí trong O(log n): mỗi bước cắt đôi khoảng cần tìm. Với 1 triệu phần tử, chỉ cần ~20 phép so sánh thay vì 1 triệu.

Ý tưởng thu hẹp khoảng [lo, hi): so giá trị giữa với mục tiêu, rồi bỏ hẳn một nửa. Điều kiện tiên quyết bắt buộc: dữ liệu phải được sắp trước — nếu không, kết quả sai một cách âm thầm.

bisect — binary search sẵn có của Python

Đừng tự viết binary search (rất dễ dính bẫy off-by-one). Python có module bisect:

• bisect_left(a, x) — trả vị trí chèn bên trái khối các phần tử bằng x. Tương đương lower_bound trong C++: điểm bắt đầu của khối bằng x.
• bisect_right(a, x) (alias bisect) — trả vị trí chèn bên phải khối bằng x. Tương đương upper_bound: ngay sau khối bằng x.
• insort_left / insort_right — tìm vị trí rồi chèn, giữ danh sách luôn sắp.

import bisect

# Ngưỡng điểm tín dụng đã sắp tăng dần — (minh hoạ)
scores = [300, 420, 550, 550, 680, 720, 800]

# Có bao nhiêu khách có điểm < 680?  -> lower_bound của 680
n_below = bisect.bisect_left(scores, 680)      # 4

# Đếm số khách có điểm đúng bằng 550 (khối trùng nhau)
lo = bisect.bisect_left(scores, 550)           # 2  (đầu khối)
hi = bisect.bisect_right(scores, 550)          # 4  (ngay sau khối)
count_550 = hi - lo                            # 2

# Xếp hạng tín dụng bằng cắt ngưỡng (bucket by threshold)
grades = [500, 650, 750]  # biên các hạng, đã sắp
def grade(score):
    idx = bisect.bisect_right(grades, score)   # số ngưỡng đã vượt
    return ["D", "C", "B", "A"][idx]

grade(700)   # 'B'  (vượt 500 và 650, chưa vượt 750)

Bẫy off-by-one và biến thể tìm biên

Ba lỗi kinh điển khi tự viết binary search: (1) dùng [lo, hi] đóng hay [lo, hi) nửa mở không nhất quán; (2) mid = (lo + hi) // 2 rồi cập nhật lo = mid gây lặp vô hạn (phải là lo = mid + 1); (3) nhầm bisect_left với bisect_right khi có phần tử trùng. Dùng bisect né được cả ba — chỉ cần nhớ rõ left = lower_bound = đầu khối, right = upper_bound = sau khối.

Binary search trên "đáp án" (search space)

Kỹ thuật nâng cao rất mạnh: khi lời giải là một số và có tính đơn điệu (nếu giá trị X thoả điều kiện thì mọi giá trị lớn hơn X cũng thoả — hoặc ngược lại), ta binary search trên miền đáp án thay vì trên mảng. Ví dụ: "tìm hạn mức nhỏ nhất sao cho tổng dư nợ không vượt vốn khả dụng". Ta không có sẵn mảng để tìm, nhưng có hàm kiểm_tra(hạn_mức) -> đủ/không đủ đơn điệu, nên cắt đôi miền hạn mức trong O(log(khoảng) × chi phí kiểm tra).

5. Use case thực tế

Top-N: xếp hạng khách hàng

Bài toán quen thuộc: lấy 10 khách có dư nợ lớn nhất từ 5 triệu bản ghi.

# Cách 1: sort toàn bộ rồi lấy N — O(n log n) — (minh hoạ)
top10 = sorted(customers, key=lambda c: c["balance"], reverse=True)[:10]

# Cách 2: heap, chỉ O(n log N) — không cần sắp toàn bộ
import heapq
top10 = heapq.nlargest(10, customers, key=lambda c: c["balance"])

Khi N nhỏ so với n, heapq.nlargest rẻ hơn vì chỉ giữ N phần tử tốt nhất — chi tiết ở Trees & heaps. Khi cần cả bảng đã sắp (không chỉ top-N), thì sorted() là đúng.

Đối soát 2 sao kê đã sắp bằng merge join — O(n) thay vì O(n²)

Đây là ví dụ đắt giá nhất của bài. Đối soát hai danh sách (sao kê nội bộ vs sao kê ngân hàng đối tác / nostro) theo cách ngây thơ: với mỗi giao dịch bên A, quét toàn bộ bên B tìm khớp → O(n × m), với vài trăm nghìn dòng mỗi bên là hàng chục tỷ phép so sánh, treo job.

Nếu cả hai đã sắp theo cùng khoá (ví dụ mã tham chiếu, hay (ngày, số tiền)), ta dùng merge join: đi hai con trỏ song song, mỗi bước tiến con trỏ có khoá nhỏ hơn — tổng chỉ O(n + m).

# Đối soát 2 sao kê đã sắp theo 'ref' — merge join O(n+m) — (minh hoạ)
def reconcile(book, bank):        # cả hai đã sort theo 'ref'
    i = j = 0
    matched, only_book, only_bank = [], [], []
    while i < len(book) and j < len(bank):
        a, b = book[i], bank[j]
        if a["ref"] == b["ref"]:
            if a["amount"] == b["amount"]:
                matched.append((a, b))
            else:
                matched.append((a, b, "LỆCH SỐ TIỀN"))
            i += 1
            j += 1
        elif a["ref"] < b["ref"]:
            only_book.append(a)   # có ở sổ, thiếu ở bank
            i += 1
        else:
            only_bank.append(b)   # có ở bank, thiếu ở sổ
            j += 1
    only_book.extend(book[i:])    # phần đuôi còn lại
    only_bank.extend(bank[j:])
    return matched, only_book, only_bank

Chi phí sắp hai bên là O(n log n) + O(m log m), rồi merge O(n + m) — vẫn thắng tuyệt đối so với O(n × m). Đây chính là cách các engine SQL thực hiện merge join, và là xương sống của quy trình đối soát kế toán. Ba nhóm kết quả (khớp, chỉ có ở sổ, chỉ có ở bank) đúng là những gì kiểm soát viên cần.

Sắp theo thời gian & khử trùng lân cận

Log giao dịch thường đến không theo thứ tự. Sắp theo timestamp trước, rồi khử trùng lân cận (dedup) — vì bản ghi trùng luôn nằm cạnh nhau sau khi sắp, chỉ cần một lượt O(n):

# Khử giao dịch trùng liền kề sau khi đã sắp theo (ts, id) — (minh hoạ)
events.sort(key=lambda e: (e["ts"], e["id"]))
deduped = []
for e in events:
    if not deduped or (e["ts"], e["id"]) != (deduped[-1]["ts"], deduped[-1]["id"]):
        deduped.append(e)

Tìm ngưỡng / percentile

Muốn biết "ngưỡng số tiền mà 95% giao dịch nằm dưới" (để đặt hạn mức cảnh báo)? Sắp danh sách rồi lấy phần tử ở vị trí 0.95 × n — đó chính là percentile. Trên dữ liệu đã sắp, tra bất kỳ percentile nào cũng là O(1); tìm "số giao dịch dưới một ngưỡng cho trước" là O(log n) bằng bisect.

6. Trong thực tế: dùng công cụ có sẵn, và external sort

Nguyên tắc thực chiến:

• Dùng sorted() / list.sort(key=...) và bisect — viết bằng C, ổn định, đúng. Chỉ tự cài thuật toán khi đang học hoặc có ràng buộc đặc biệt.
• key= thay vì cmp — Python 3 bỏ tham số so sánh; hàm key chỉ gọi một lần mỗi phần tử, hiệu quả hơn.
• Dữ liệu lớn hơn RAM → external sort. Khi không nạp hết vào bộ nhớ, chia thành nhiều mảnh vừa RAM, sắp từng mảnh, ghi ra đĩa, rồi k-way merge các mảnh đã sắp (chính là mở rộng của merge join). Bạn hiếm khi tự viết: giao cho Polars, DuckDB hay Spark — chúng làm spill-to-disk và merge sort ngoài rất tốt. Hiểu nguyên lý giúp bạn biết vì sao một ORDER BY trên bảng khổng lồ lại tốn đĩa tạm.

Ghi nhớ

• Sắp xếp dựa so sánh không thể nhanh hơn Ω(n log n) (chứng minh bằng cây quyết định, n! lá). Muốn O(n) phải không so sánh — counting/radix/bucket khi miền giá trị hẹp.
• Merge sort: ổn định, worst-case O(n log n), tốn O(n) bộ nhớ. Quicksort: in-place, trung bình O(n log n) nhưng worst-case O(n²), không ổn định.
• Python dùng Timsort: ổn định, worst-case O(n log n), thích nghi với dữ liệu gần sắp. Dùng sorted(), đừng tự viết.
• Ổn định cho phép sắp nhiều khoá bằng cách sắp nhiều lần (khoá phụ trước, khoá chính sau).
• Binary search O(log n) chỉ đúng trên dữ liệu đã sắp. Dùng bisect: bisect_left = lower_bound (đầu khối), bisect_right = upper_bound (sau khối). Né được bẫy off-by-one.
• Binary search trên đáp án khi lời giải đơn điệu (tìm ngưỡng/hạn mức).
• Use case: top-N (sort hoặc heapq.nlargest), đối soát 2 danh sách đã sắp bằng merge join O(n+m) thay vì O(n²), khử trùng lân cận, tìm percentile bằng bisect.
• Dữ liệu vượt RAM → external sort (chia mảnh, sort, k-way merge); trong thực tế giao cho Polars/DuckDB/Spark.

Bài liên quan: Độ phức tạp · Cấu trúc dữ liệu · Trees & heaps · Đối soát kế toán