Quick sort (Sắp xếp nhanh)

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

Quick sort là thuật toán sắp xếp nhanh nhất trong thực tế trên hầu hết dữ liệu. Ý tưởng: chọn một phần tử làm chốt (pivot), phân hoạch (partition) mảng thành "nhỏ hơn pivot" và "lớn hơn pivot", rồi sắp đệ quy hai phần. Trung bình O(n log n), nhưng xấu nhất tụt xuống O(n^2) — và bạn sẽ học mẹo chọn pivot để gần như không bao giờ gặp trường hợp xấu.

1. Trực quan: chia phòng theo chiều cao

Hình dung một lớp học đang xếp hàng lộn xộn. Bạn chọn đại một bạn làm mốc (pivot). Rồi bạn hô: "Ai thấp hơn bạn này, sang trái! Ai cao hơn, sang phải!". Sau một lượt, bạn mốc đã đứng đúng vị trí cuối cùng của mình — bên trái toàn người thấp hơn, bên phải toàn người cao hơn. Giờ chỉ cần lặp lại trò này cho nhóm trái và nhóm phải.

chon pivot = 5
[5 3 8 1 9 2]
   phan hoach quanh 5:
[3 1 2] [5] [8 9]          <- 5 da dung cho vinh vien
  |          |
de quy trai   de quy phai
[1 2 3] [5] [8 9]          <- ghep lai -> da sap

Điểm hay: khác merge sort (làm việc khi trộn lên), quick sort làm việc khi chia xuống — sau khi phân hoạch, pivot không bao giờ phải động tới nữa.

2. Ý tưởng cốt lõi: pivot + phân hoạch

Thuộc tính	Giá trị	Ghi chú
Trung bình	O(n log n)	pivot chia tương đối đều
Xấu nhất	O(n^2)	pivot luôn rơi vào nhỏ nhất/lớn nhất
Bộ nhớ	O(log n)	chỉ tốn ngăn xếp đệ quy (sắp gần như tại chỗ)
Ổn định	Không	phân hoạch có thể đảo thứ tự phần tử bằng nhau

Trường hợp xấu xảy ra khi pivot luôn là phần tử nhỏ nhất (hoặc lớn nhất) — ví dụ mảng đã sắp sẵn mà ta cứ chọn pivot là phần tử cuối. Khi đó mỗi lần chỉ tách được 1 phần tử → n tầng → O(n^2). Cách né: chọn pivot ngẫu nhiên hoặc lấy trung vị của ba (median-of-three).

3. Chạy debug: phân hoạch quanh pivot = 5

Xem một lượt phân hoạch chia mảng quanh pivot.

🐞 Phân hoạch [3, 8, 1, 9, 2] quanh pivot = 5Bước 1/5

1pivot = 5
2nho  = [x for x in a if x < pivot]
3bang = [x for x in a if x == pivot]
4lon  = [x for x in a if x > pivot]
5ket_qua = nho + bang + lon

Biến tại bước này

a	[3, 8, 1, 9, 2, 5]
pivot	5

👉 Chọn pivot = 5.

4. Code chạy được

Phiên bản dễ đọc (dùng list comprehension) và phiên bản tại chỗ (Lomuto) với pivot ngẫu nhiên.

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

5. Phân tích: nhanh nhưng phải cẩn thận với pivot

• Vì sao trung bình O(n log n)? Nếu pivot chia mảng tương đối đều, ta có ~log n tầng, mỗi tầng phân hoạch tốn O(n) → O(n log n), giống merge sort.
• Vì sao xấu nhất O(n^2)? Nếu pivot luôn lệch hẳn về một đầu (mảng đã sắp + chọn pivot cuối), mỗi lần chỉ bóc được 1 phần tử → n tầng.
• Cách phòng vệ: pivot ngẫu nhiên hoặc median-of-three (lấy trung vị của phần tử đầu, giữa, cuối). Xác suất gặp trường hợp xấu trở nên cực nhỏ.
• Bộ nhớ O(log n): quick sort sắp gần như tại chỗ, chỉ tốn ngăn xếp đệ quy — đây là lợi thế lớn so với merge sort O(n).
• Bẫy thường gặp: quên rằng quick sort không ổn định; nếu cần ổn định, dùng merge sort.

6. Mẫu nhận diện

• Cần sắp xếp nhanh trong thực tế, không quá lo về trường hợp xấu lý thuyết → quick sort.
• Tiết kiệm bộ nhớ (không muốn mảng phụ O(n)) → quick sort hơn merge sort.
• Dữ liệu có thể đã sắp sẵn hoặc đối thủ cố tình làm xấu → nhớ pivot ngẫu nhiên/median-of-three.
• Bài toán "tìm phần tử lớn thứ k" → biến thể quickselect dùng đúng ý tưởng phân hoạch này.

7. 🎮 Trò chơi: Hiểu quick sort

🎮 Quick sort & pivotCâu 1/4· Điểm 0· 🔥 0

Phân hoạch quanh pivot. Trung bình O(n log n), xấu nhất O(n^2). Chọn pivot khôn ngoan!

Độ phức tạp TRUNG BÌNH của quick sort là?

8. Quiz kiểm tra nhanh

📝 Quiz kiểm tra nhanh

1. Bước cốt lõi của quick sort tên là gì?

2. So với merge sort, ưu thế bộ nhớ của quick sort là?

3. Quick sort có phải thuật toán ổn định không?

9. Hoàn thành

…

☑️ Tiếp theo: 3.1.4 — Heap sort (dùng cấu trúc max-heap để sắp tại chỗ).