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
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
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.