Giao diện
Tổng Quan Về Thuật Toán Sắp Xếp (Sorting)
Sorting (Sắp xếp) là quá trình sắp xếp các phần tử trong một danh sách theo một thứ tự nhất định (thường là tăng dần hoặc giảm dần). Đây là một trong những bài toán cơ bản và quan trọng nhất trong Khoa Học Máy Tính.
Tại sao chúng ta cần học Sorting? Không chỉ để "phỏng vấn", mà việc hiểu cách dữ liệu được sắp xếp giúp bạn tối ưu hóa việc tìm kiếm (Search), quản lý cơ sở dữ liệu, và xử lý dữ liệu lớn (Big Data).
Khái Niệm Quan Trọng: Stability (Tính Ổn Định)
Một thuật toán sắp xếp được gọi là Stable (Ổn định) 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 (key).
Ví dụ Trực Quan (Bộ Bài Tây)
Hãy tưởng tượng bạn có một bộ bài, và bạn đang sắp xếp chúng.
- Input: 5♠, 3♥, 5♦, 2♣
- Bạn muốn sắp xếp theo thứ tự tăng dần của số (Rank).
Nếu thuật toán là Stable:
- Output: 2♣, 3♥, 5♠, 5♦
- Giải thích: 5♠ đứng
trước5♦ trong Input, nên nó vẫn đứngtrước5♦ trong Output. Thứ tự "chất" được bảo toàn.
Nếu thuật toán là Unstable:
- Output: 2♣, 3♥, 5♦, 5♠
- Giải thích: Thứ tự của hai lá bài 5 đã bị đảo lộn.
Tại sao Stability quan trọng?
Trong thực tế, khi bạn sort một danh sách Excel theo "Tên" rồi sau đó sort theo "Lớp", một thuật toán Stable sẽ đảm bảo rằng trong cùng một "Lớp", các học sinh vẫn được sắp xếp theo "Tên" như bước trước đó. Unstable sort sẽ làm mất trật tự này.
So Sánh Các Thuật Toán Cơ Bản (Basic Sorting)
Chúng ta sẽ bắt đầu hành trình với 3 thuật toán "nhập môn". Dù chúng không nhanh nhất (O(N^2)), nhưng chúng là nền tảng tư duy thuật toán.
| Thuật Toán | Best Case | Average Case | Worst Case | Space Complexity | Stable? |
|---|---|---|---|---|---|
| Bubble Sort | O(N) | O(N^2) | O(N^2) | O(1) | ✅ Yes |
| Insertion Sort | O(N) | O(N^2) | O(N^2) | O(1) | ✅ Yes |
| Selection Sort | O(N^2) | O(N^2) | O(N^2) | O(1) | ❌ No |
Production-Grade Sorting
Các thuật toán được sử dụng trong production và thư viện chuẩn:
| Thuật Toán | Best Case | Average Case | Worst Case | Space | Stable? | Dùng trong |
|---|---|---|---|---|---|---|
| Timsort | O(N) | O(N log N) | O(N log N) | O(N) | ✅ Yes | Python, Java, Swift |
| Radix Sort | O(NK) | O(NK) | O(NK) | O(N+K) | ✅ Yes | Integer/String sort |
| Counting Sort | O(N+K) | O(N+K) | O(N+K) | O(K) | ✅ Yes | Small range integers |
HPN nhắc nhở
Đừng bao giờ coi thường các thuật toán O(N^2). Trong các hệ thống thực tế (như thư viện chuẩn của Python hay Java), Insertion Sort thường được dùng kết hợp với Merge Sort hoặc Quick Sort (gọi là Timsort hoặc Introsort) để xử lý các mảng con kích thước nhỏ vì nó cực kỳ nhanh và ít overhead!