Giao diện
Thuật toán Sắp xếp 🔢
Sắp xếp là bài toán được nghiên cứu nhiều nhất trong lịch sử Khoa học Máy tính. Không phải vì nó đơn giản — mà vì nó xuất hiện ở khắp nơi: database engine dùng sort để tổ chức index, hệ điều hành dùng sort để lập lịch process, trình biên dịch dùng sort để tối ưu register allocation. Hiểu sắp xếp là hiểu nền tảng của mọi hệ thống xử lý dữ liệu.
Từ những thuật toán O(n²) dễ hiểu đến O(n log n) hiệu quả, rồi đến O(n·k) phá vỡ giới hạn comparison-based — mỗi thuật toán dạy bạn một tư duy khác nhau: brute force, chia để trị, cấu trúc dữ liệu, và exploitation đặc tính phân bố. Nắm vững chúng, bạn sẽ có bộ công cụ tư duy mạnh mẽ cho mọi bài toán thuật toán.
Lộ trình học
💡 Khuyến nghị
Đi theo thứ tự dưới đây. Mỗi thuật toán xây dựng trên kiến thức của thuật toán trước.
Phase 1 — Nền tảng O(n²)
Mục tiêu: hiểu cơ chế so sánh, hoán đổi, và khái niệm stability.
- Bubble Sort — Trực quan nhất. Học cách tối ưu dần từ brute force bằng early termination.
- Selection Sort — Tối thiểu số lần ghi bộ nhớ (O(n) swap). Hiểu trade-off giữa so sánh và ghi.
- Insertion Sort — Nhanh nhất trong nhóm O(n²) cho dữ liệu gần sorted. Xương sống của Timsort.
Phase 2 — Chia để trị O(n log n)
Mục tiêu: nắm kỹ thuật divide-and-conquer và phân tích đệ quy.
- Merge Sort — Luôn O(n log n), stable, nền tảng của external sorting. Dạy bạn kỹ thuật merge.
- Quick Sort — Nhanh nhất trung bình trong thực tế. Dạy partition, pivot strategy, và randomized algorithm.
- Heap Sort — O(n log n) worst-case với O(1) space. Dạy cấu trúc heap — dùng lại cho priority queue.
Phase 3 — Production & Chuyên sâu
Mục tiêu: hiểu thuật toán production-grade và phá vỡ giới hạn O(n log n).
- Timsort — Hybrid sort dùng trong Python, Java, Swift. Kết hợp Merge Sort + Insertion Sort với khai thác run tự nhiên.
- Radix Sort & Counting Sort — Non-comparison sort. Đạt O(n·k) bằng cách khai thác cấu trúc key thay vì so sánh.
Bảng so sánh tổng hợp
| Thuật toán | Best | Average | Worst | Space | Stable | In-place | Ghi chú |
|---|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ | ✅ | Adaptive nếu có early termination |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | ❌ | ✅ | Chỉ O(n) swap — tốt cho flash memory |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ | ✅ | Tốt nhất cho n nhỏ và dữ liệu gần sorted |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ | ❌ | Predictable, dùng cho external sort |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ | ✅ | Nhanh nhất trung bình, cache-friendly |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ | ✅ | O(1) space + O(n log n) guaranteed |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | ✅ | ❌ | Default sort của Python, Java, Swift |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | ✅ | ❌ | k = range giá trị, chỉ cho integer |
| Radix Sort | O(n · d) | O(n · d) | O(n · d) | O(n + k) | ✅ | ❌ | d = số chữ số, k = base (thường 10) |
📝 Chú thích
- Stable: giữ nguyên thứ tự tương đối của phần tử có cùng giá trị
- In-place: chỉ dùng O(1) bộ nhớ phụ (không tính call stack)
- Adaptive: chạy nhanh hơn khi input đã gần sorted
Cách chọn thuật toán
Không có thuật toán "tốt nhất" cho mọi trường hợp. Quyết định dựa trên đặc tính dữ liệu:
| Tình huống | Thuật toán khuyên dùng | Lý do |
|---|---|---|
| Mảng nhỏ (n ≤ 50) | Insertion Sort | Overhead thấp, cache-friendly, adaptive |
| Dữ liệu gần sorted | Insertion Sort hoặc Timsort | O(n) best-case cho dữ liệu gần đúng thứ tự |
| Cần stable sort + hiệu quả | Merge Sort hoặc Timsort | Guaranteed O(n log n) + stable |
| Cần in-place + hiệu quả | Quick Sort hoặc Heap Sort | O(log n) hoặc O(1) extra space |
| Integer với range nhỏ | Counting Sort | O(n + k), nhanh hơn comparison sort |
| Integer/String với key cố định | Radix Sort | O(n · d), phá vỡ giới hạn O(n log n) |
| Bộ nhớ hạn chế, cần worst-case guaranteed | Heap Sort | O(1) space + O(n log n) worst-case |
| Dữ liệu lớn không fit RAM | Merge Sort (external) | Sequential access, merge từng chunk |
| Không biết gì về dữ liệu | Quick Sort (randomized pivot) | Trung bình nhanh nhất, cache-friendly |
⚡ Quy tắc ngón tay cái
Nếu bạn không chắc chắn, dùng sort mặc định của ngôn ngữ (thường là Timsort hoặc Introsort). Chúng đã được tối ưu cho hầu hết trường hợp thực tế. Chỉ tự implement khi có lý do cụ thể.
Khái niệm nền tảng
Trước khi đi vào từng thuật toán, nắm vững các khái niệm cốt lõi:
→ Tổng quan về Sắp xếp — Stability, comparison vs distribution sort, O(n log n) lower bound, và các phân loại quan trọng.
🧠 Quiz
Câu 1: Timsort (thuật toán sắp xếp mặc định của Python và Java) kết hợp những thuật toán nào?
- [ ] A) Quick Sort + Heap Sort
- [x] B) Merge Sort + Insertion Sort
- [ ] C) Bubble Sort + Selection Sort
- [ ] D) Radix Sort + Counting Sort
💡 Giải thích: Timsort phát hiện các "run" (đoạn đã sắp xếp) trong dữ liệu, dùng Insertion Sort cho đoạn nhỏ (< 64), rồi merge các run bằng Merge Sort. Kết hợp ưu điểm: adaptive O(n) cho dữ liệu gần sắp xếp, worst case O(n log n).
Câu 2: Thuật toán sắp xếp nào KHÔNG dựa trên comparison (so sánh)?
- [ ] A) Merge Sort
- [ ] B) Quick Sort
- [x] C) Counting Sort và Radix Sort
- [ ] D) Heap Sort
💡 Giải thích: Comparison-based sort có lower bound Ω(n log n). Counting Sort và Radix Sort phá rào này bằng cách không so sánh trực tiếp — thay vào đó đếm hoặc phân phối theo digit/bucket → O(n×k) hoặc O(n×d). Trade-off: cần biết range của dữ liệu.
Câu 3: Khi nào Quick Sort có worst case O(n²)?
- [ ] A) Khi mảng có phần tử trùng
- [x] B) Khi pivot luôn là phần tử nhỏ nhất hoặc lớn nhất (mảng đã sắp xếp + chọn pivot đầu/cuối)
- [ ] C) Khi mảng hoàn toàn ngẫu nhiên
- [ ] D) Quick Sort không bao giờ O(n²)
💡 Giải thích: Nếu pivot luôn chia mảng thành 0 và n-1 phần tử (thay vì ~n/2 và ~n/2), Quick Sort suy biến thành O(n²). Xảy ra khi mảng đã sắp xếp + chọn pivot = first/last. Giải pháp: random pivot, median-of-three, hoặc dùng Introsort.