Giao diện
Tổng quan về Sắp xếp
Trước khi đi vào từng thuật toán cụ thể, bạn cần nắm vững các khái niệm phân loại mà mọi kỹ sư dùng để đánh giá và lựa chọn thuật toán sắp xếp. Trang này tập trung vào lý thuyết nền tảng — những kiến thức sẽ theo bạn xuyên suốt toàn bộ section.
Stability — Tính ổn định
Một thuật toán được gọi là stable nếu nó giữ nguyên thứ tự tương đối của các phần tử có cùng giá trị khóa sắp xếp.
Ví dụ trực quan
Giả sử bạn có danh sách sinh viên đã sắp xếp theo tên:
Input (đã sort theo tên):
An - Lớp B
Bình - Lớp A
Cường - Lớp A
Dũng - Lớp BBây giờ bạn sort lại theo lớp:
Stable sort → giữ thứ tự tên trong cùng lớp:
Bình - Lớp A ← Bình trước Cường (giữ nguyên)
Cường - Lớp A
An - Lớp B ← An trước Dũng (giữ nguyên)
Dũng - Lớp B
Unstable sort → thứ tự tên có thể bị đảo:
Cường - Lớp A ← Cường trước Bình (đảo!)
Bình - Lớp A
Dũng - Lớp B
An - Lớp BTại sao stability quan trọng?
Stability cho phép bạn sort nhiều lần theo nhiều tiêu chí — sort theo tiêu chí phụ trước, tiêu chí chính sau. Nếu thuật toán stable, kết quả cuối cùng sẽ đúng cho cả hai tiêu chí. Đây là nền tảng của multi-key sorting trong database và spreadsheet.
Phân loại
| Stable | Unstable |
|---|---|
| Bubble Sort, Insertion Sort, Merge Sort, Timsort, Counting Sort, Radix Sort | Selection Sort, Quick Sort, Heap Sort |
Comparison-based vs Distribution-based
Đây là ranh giới quan trọng nhất trong phân loại thuật toán sắp xếp.
Comparison-based sort
Chỉ sử dụng phép so sánh giữa hai phần tử (a < b, a > b, a = b) để quyết định thứ tự. Không cần biết gì về cấu trúc nội tại của dữ liệu.
Ví dụ: Bubble Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort, Timsort.
Giới hạn: Bị ràng buộc bởi lower bound Ω(n log n) — không thể nhanh hơn dù thiết kế thế nào (chứng minh ở phần sau).
Distribution-based sort (Non-comparison)
Khai thác cấu trúc của key (số chữ số, range giá trị) để phân phối phần tử vào đúng vị trí mà không cần so sánh trực tiếp.
Ví dụ: Counting Sort, Radix Sort, Bucket Sort.
Ưu điểm: Có thể đạt O(n) hoặc O(n·d), phá vỡ giới hạn O(n log n).
Hạn chế: Chỉ áp dụng được khi key có cấu trúc cụ thể (integer, string có độ dài cố định). Không dùng được cho dữ liệu chỉ hỗ trợ phép so sánh (ví dụ: so sánh hai object tùy ý).
Giới hạn dưới O(n log n) — Decision Tree Argument
Đây là một trong những kết quả đẹp nhất của lý thuyết thuật toán:
Mọi thuật toán sắp xếp dựa trên so sánh đều cần ít nhất Ω(n log n) phép so sánh trong trường hợp xấu nhất.
Chứng minh trực quan
Mô hình hóa thuật toán sắp xếp như một cây quyết định (decision tree):
- Mỗi nút trong là một phép so sánh: "a[i] ≤ a[j]?"
- Mỗi nhánh là kết quả Yes/No.
- Mỗi lá là một hoán vị (permutation) cụ thể — kết quả sắp xếp.
Với n phần tử, có n! hoán vị khả dĩ → cây phải có ít nhất n! lá.
Một cây nhị phân có h tầng chứa tối đa 2^h lá. Do đó:
2^h ≥ n!
→ h ≥ log₂(n!)
→ h ≥ n·log₂(n) - n·log₂(e) (xấp xỉ Stirling)
→ h = Ω(n log n)Ý nghĩa thực tiễn: Merge Sort và Heap Sort đạt O(n log n) worst-case — chúng đã tối ưu tiệm cận. Bạn không thể thiết kế thuật toán comparison-based nào nhanh hơn về mặt lý thuyết.
💡 Vượt qua giới hạn
Counting Sort và Radix Sort đạt được O(n) vì chúng không dựa trên so sánh. Chúng khai thác thông tin bổ sung về key (range, số chữ số) — điều mà decision tree argument không áp dụng.
Adaptive vs Non-adaptive
Adaptive sort chạy nhanh hơn khi input đã gần đúng thứ tự (partially sorted).
| Đặc tính | Adaptive | Non-adaptive |
|---|---|---|
| Định nghĩa | Tận dụng "thứ tự sẵn có" trong input | Luôn mất cùng số bước bất kể input |
| Best-case | Tốt hơn đáng kể so với average | Gần bằng average |
| Ví dụ | Insertion Sort: O(n) khi sorted | Selection Sort: luôn O(n²) |
Timsort là ví dụ xuất sắc: nó quét input tìm các đoạn đã sorted ("run") rồi merge chúng. Nếu input có nhiều run dài, Timsort tiệm cận O(n).
Tại sao adaptive quan trọng? Trong thực tế, dữ liệu hiếm khi ngẫu nhiên hoàn toàn. Log file gần như sorted theo timestamp. Danh sách user thêm một vài record mới vào cuối vẫn gần sorted. Thuật toán adaptive khai thác đặc tính này để chạy nhanh hơn nhiều.
In-place vs Out-of-place
| Đặc tính | In-place | Out-of-place |
|---|---|---|
| Extra space | O(1) hoặc O(log n) cho call stack | O(n) hoặc hơn |
| Ưu điểm | Tiết kiệm bộ nhớ | Dễ implement, thường stable |
| Nhược điểm | Implement phức tạp hơn, thường unstable | Tốn bộ nhớ gấp đôi |
| Ví dụ | Quick Sort, Heap Sort, Insertion Sort | Merge Sort, Counting Sort, Radix Sort |
Lưu ý: "In-place" trong ngữ cảnh sorting thường chấp nhận O(log n) cho call stack đệ quy (Quick Sort). Nếu yêu cầu nghiêm ngặt O(1), chỉ còn Heap Sort, Selection Sort, Insertion Sort, và Bubble Sort.
⚡ Trade-off kinh điển
Merge Sort stable + O(n log n) nhưng cần O(n) space. Quick Sort in-place nhưng unstable + O(n²) worst-case. Heap Sort in-place + O(n log n) guaranteed nhưng unstable + cache-unfriendly. Không thuật toán nào hoàn hảo — chỉ có thuật toán phù hợp nhất cho context cụ thể.
Internal sort vs External sort
| Đặc tính | Internal sort | External sort |
|---|---|---|
| Dữ liệu | Fit hoàn toàn trong RAM | Lớn hơn RAM, lưu trên disk |
| Tối ưu cho | Random access nhanh | Sequential access (giảm I/O) |
| Thuật toán điển hình | Quick Sort, Heap Sort, Timsort | External Merge Sort |
| Bottleneck | CPU (phép so sánh) | Disk I/O (đọc/ghi) |
External Merge Sort hoạt động thế nào?
- Chia: đọc từng chunk fit RAM, sort bằng internal sort, ghi ra file tạm.
- Merge: merge các file tạm đã sorted bằng k-way merge (dùng min-heap).
- Lặp: nếu số file tạm vẫn quá lớn, lặp lại bước merge cho đến khi còn 1 file.
Merge Sort phù hợp cho external sorting vì nó truy cập dữ liệu tuần tự — đúng đặc tính của disk I/O. Quick Sort ngược lại truy cập random, gây thrashing khi dữ liệu trên disk.
Tổng kết phân loại
| Tiêu chí | Phân loại | Câu hỏi cần trả lời |
|---|---|---|
| Cơ chế | Comparison vs Distribution | Thuật toán có dùng phép so sánh? |
| Stability | Stable vs Unstable | Có giữ thứ tự phần tử bằng nhau? |
| Adaptivity | Adaptive vs Non-adaptive | Có nhanh hơn khi input gần sorted? |
| Bộ nhớ | In-place vs Out-of-place | Cần bao nhiêu extra space? |
| Vị trí dữ liệu | Internal vs External | Dữ liệu fit trong RAM hay trên disk? |
Nắm vững 5 tiêu chí này, bạn sẽ đọc hiểu và đánh giá được bất kỳ thuật toán sắp xếp nào — kể cả những thuật toán bạn chưa từng gặp.
Bước tiếp theo
Đã sẵn sàng? Bắt đầu với thuật toán đầu tiên → Bubble Sort
🧠 Quiz
Câu 1: Thuật toán sắp xếp nào là "stable" (ổn định)?
- [ ] A) Quick Sort (implementation chuẩn)
- [ ] B) Heap Sort
- [x] C) Merge Sort, Insertion Sort, Bubble Sort, Timsort
- [ ] D) Selection Sort
💡 Giải thích: Stable sort giữ nguyên thứ tự tương đối của các phần tử bằng nhau. Merge Sort (merge giữ thứ tự), Insertion Sort (chỉ dịch khi >), Bubble Sort (chỉ swap khi >), Timsort (dựa trên Merge Sort). Quick Sort và Heap Sort không stable theo mặc định.
Câu 2: "In-place" sorting nghĩa là gì?
- [ ] A) Sắp xếp tại chỗ không cần máy tính
- [x] B) Chỉ dùng O(1) bộ nhớ phụ (không tạo mảng mới)
- [ ] C) Sắp xếp trong một pass duy nhất
- [ ] D) Không thay đổi mảng gốc
💡 Giải thích: In-place sort thao tác trực tiếp trên mảng input, chỉ dùng O(1) extra space (vài biến tạm). Quick Sort, Heap Sort, Insertion Sort là in-place. Merge Sort cần O(n) extra space cho mảng tạm khi merge — KHÔNG in-place (trừ biến thể phức tạp).