Chuyển tới nội dung chính

Ổn định & so sánh các thuật toán sắp xếp

Bạn sẽ học được gì

Bạn đã có trong tay sáu thuật toán sắp xếp. Bài này tổng kết: hiểu rõ tính ổn định (stable) — một tính chất tinh tế nhưng cực kỳ quan trọng trong thực tế — và có một bảng so sánh đầy đủ để chọn đúng thuật toán cho từng tình huống.

1. Trực quan: ổn định nghĩa là "không xáo trộn người ngang điểm"​

Tưởng tượng một bảng xếp hạng học sinh đang sắp theo tên (A, B, C...). Giờ sếp bảo: "Sắp lại theo điểm số". Có hai bạn cùng 8 điểm: An (đứng trước) và Bình (đứng sau).

  • Thuật toán ổn định (stable): sau khi sắp theo điểm, An vẫn đứng trước Bình. Thứ tự cũ giữa hai người ngang điểm được giữ nguyên.
  • Thuật toán không ổn định (unstable): có thể Bình bị nhảy lên trước An. Hai người ngang điểm bị xáo trộn so với thứ tự ban đầu.
Goc (da sap theo TEN):  An:8   Binh:8   Cuong:7

Sap theo DIEM giam dan:
   On dinh   ->  An:8   Binh:8   Cuong:7    (An van truoc Binh)
   Khong on dinh -> Binh:8  An:8   Cuong:7  (bi dao!)

Tính ổn định quan trọng khi ta sắp nhiều tầng: sắp theo tên trước, rồi sắp theo điểm. Chỉ thuật toán ổn định mới giữ được "trong cùng điểm thì theo tên".

2. Vì sao ổn định lại quan trọng trong thực tế​

Bạn hiếm khi sắp một danh sách số đơn thuần. Thực tế là sắp các bản ghi nhiều trường: đơn hàng có (ngày, khách, giá), nhân viên có (phòng, tên, lương)... Khi đó:

  • Sắp đa tiêu chí bằng cách sắp lần lượt từ tiêu chí phụ tới tiêu chí chính, dựa vào tính ổn định để các tầng trước không bị phá.
  • Kết quả dễ đoán, lặp lại được — quan trọng cho kiểm thử và trải nghiệm người dùng (bảng không "nhảy lung tung" mỗi lần sắp lại).

3. Chạy debug: thấy tính ổn định "sống"​

Sắp các cặp (chu, so) theo so. Hai cặp cùng số là ("a", 2) và ("c", 2) — thuật toán ổn định giữ a trước c.

🐞 Sắp [(a,2),(b,1),(c,2)] theo số, giữ ổn địnhBước 1/4
1data = [("a", 2), ("b", 1), ("c", 2)]
2# sap on dinh theo phan tu thu 2 (so)
3ket_qua = sorted(data, key=lambda t: t[1])
4# so 1 truoc: (b,1)
5# cac so 2: giu nguyen thu tu goc a truoc c
6# -> [(b,1), (a,2), (c,2)]
Biến tại bước này
data[(a,2), (b,1), (c,2)]
👉 Thứ tự gốc: a trước c (cả hai cùng số 2).

4. Kiểm chứng bằng code​

Đang tải trình chạy code…

5. Bảng so sánh đầy đủ​

Thuật toánTốt nhấtTrung bìnhXấu nhấtBộ nhớỔn địnhKhi nào dùng
BubbleO(n)O(n^2)O(n^2)O(1)CóDạy học; mảng tí hon
SelectionO(n^2)O(n^2)O(n^2)O(1)KhôngKhi số phép đổi chỗ phải ít nhất
InsertionO(n)O(n^2)O(n^2)O(1)CóMảng nhỏ hoặc gần như đã sắp
MergeO(n log n)O(n log n)O(n log n)O(n)CóCần ổn định + đảm bảo O(n log n); linked list
QuickO(n log n)O(n log n)O(n^2)O(log n)KhôngNhanh thực tế; tiết kiệm bộ nhớ
HeapO(n log n)O(n log n)O(n log n)O(1)KhôngĐảm bảo O(n log n) + O(1) bộ nhớ
CountingO(n + k)O(n + k)O(n + k)O(n + k)CóKhóa nguyên, dải k nhỏ
RadixO(d(n + k))O(d(n + k))O(d(n + k))O(n + k)CóSố nguyên/chuỗi độ dài cố định

(Hai dòng cuối — Counting/Radix — là sắp xếp phi so sánh, học kỹ ở bài 3.1.6).

6. Cách chọn nhanh trong đầu​

  • Mảng nhỏ / gần sắp → insertion.
  • Cần ổn định và đảm bảo tốc độ → merge.
  • Muốn nhanh, ít bộ nhớ, không cần ổn định → quick (nhớ pivot ngẫu nhiên).
  • Cần O(n log n) đảm bảo và O(1) bộ nhớ → heap.
  • Khóa là số nguyên dải hẹp → counting/radix (vượt mốc O(n log n)).

7. 🎮 Trò chơi: Ổn định & lựa chọn​

🎮 Tính ổn định & so sánhCâu 1/4· Điểm 0· 🔥 0

Ổn định = giữ thứ tự gốc giữa các phần tử bằng nhau. Mỗi thuật toán có chỗ dùng riêng.

Thuật toán "ổn định" (stable) nghĩa là gì?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Ba thuật toán nào sau đây là ỔN ĐỊNH?
2. Vì sao tính ổn định quan trọng khi sắp ĐA TIÊU CHÍ?
3. Thuật toán nào có xấu nhất O(n^2) (khác với các O(n log n) còn lại)?

9. Hoàn thành​

…

☑️ Tiếp theo: 3.1.6 — Sắp xếp phi so sánh (Counting, Radix, Bucket — vượt mốc O(n log n)).