Làm thế nào để chọn giữa các thuật toán sắp xếp?

Question

Accepted Answer

Việc chọn một thuật toán sắp xếp quy về một vài thuộc tính: **độ phức tạp thời gian**, **tính ổn định**, **mức dùng bộ nhớ tại chỗ**, và bản chất của dữ liệu. Không một thuật toán sắp xếp nào thắng ở mọi nơi.

## Các thuộc tính chính

- **Ổn định (Stable):** các phần tử bằng nhau giữ nguyên thứ tự tương đối ban đầu (cần thiết cho sắp xếp theo nhiều khóa).
- **Tại chỗ (In-place):** dùng bộ nhớ phụ O(1) hoặc O(log n).
- **Thích nghi (Adaptive):** nhanh hơn trên đầu vào gần như đã sắp xếp.

## So sánh

| Thuật toán | Thời gian TB | Xấu nhất | Ổn định | Tại chỗ |
|-----------|----------|-------|--------|----------|
| Insertion | O(n²) | O(n²) | Có | Có |
| Merge | O(n log n) | O(n log n) | Có | Không |
| Quick | O(n log n) | O(n²) | Không | Có |
| Heap | O(n log n) | O(n log n) | Không | Có |

## Hướng dẫn

- **Nhỏ / gần như đã sắp xếp** -> insertion sort.
- **Cần tính ổn định hoặc O(n log n) được đảm bảo** -> merge sort.
- **Nhanh trong bộ nhớ nói chung, tốc độ trung bình quan trọng** -> quicksort (pivot ngẫu nhiên).
- **Cần giới hạn đảm bảo + bộ nhớ chật hẹp** -> heap sort.

```python
# Hầu hết các ngôn ngữ đều có sẵn một thuật toán lai đã được tinh chỉnh; hãy ưu tiên nó trong production
sorted(data, key=lambda x: x.priority)   # Timsort ổn định trong Python
```

## Những cạm bẫy

Đừng tự viết tay một thuật toán sắp xếp trừ khi bạn có lý do cụ thể — các thuật toán sắp xếp thư viện (Timsort, introsort) là các thuật toán lai đã được thử thách qua thực chiến.

## Tại sao điều này quan trọng

Khớp thuật toán sắp xếp với dữ liệu và yêu cầu giúp tránh cả việc lãng phí thời gian lẫn các lỗi tinh vi (như làm mất tính ổn định).

Hiểu các đánh đổi giải thích vì sao các thư viện chuẩn chọn các thuật toán lai như Timsort và introsort.

Khả năng phán đoán so sánh này — chứ không phải ghi nhớ một thuật toán — là điều mà kỹ thuật thực thụ và phỏng vấn tưởng thưởng.

Thuật toán	Thời gian TB	Xấu nhất	Ổn định	Tại chỗ
Insertion	O(n²)	O(n²)	Có	Có
Merge	O(n log n)	O(n log n)	Có	Không
Quick	O(n log n)	O(n²)	Không	Có
Heap	O(n log n)	O(n log n)	Không	Có