Lesson 08 — Quicksort
3 module tương tác: (1) Partition animator — xem Lomuto vs Hoare đẩy phần tử về 2 phía từng bước; (2) Quicksort tree — cây đệ quy partition, mỗi level đóng đinh 1 pivot; (3) Pivot strategy — vì sao sorted input giết pivot=last (O(n²)) nhưng random/median cứu được.
1. Partition animator — Lomuto vs Hoare
Chọn sơ đồ Lomuto hoặc Hoare rồi chạy từng bước — xem con trỏ chia mảng quanh pivot.
so sánh: 0 · swap: 0
pivot
con trỏ (i/j)
≤ pivot
> pivot
Chọn sơ đồ và bấm Bước tiếp để xem partition đẩy phần tử về 2 phía.
2. Quicksort tree — cây đệ quy partition
tổng so sánh: 0
pivot (đóng đinh đúng chỗ)
phần < pivot
phần > pivot
Mỗi node = 1 lời gọi quicksort. Pivot (cam) sau partition nằm đúng vị trí cuối cùng; 2 con là 2 phần đệ quy. Lomuto, pivot = phần tử cuối.
3. Pivot strategy — sorted input giết pivot=last
Thử: đưa mảng ĐÃ SORT với pivot = cuối — cây partition lệch thành chuỗi, O(n²); đổi pivot random — cây cân lại, O(n log n).
Chọn đã sort tăng dần + bấm So sánh: pivot=last suy biến về
O(n²) (cột đỏ dài, depth ≈ n), còn random/median giữ O(n log n) (depth ≈ log n). Đổi sang ngẫu nhiên để thấy cả ba xấp xỉ nhau.