Cùng một bài, đọc bằng chữ. Nhanh hơn và tìm lại được bằng Ctrl+F.
Một lượt phân hoạch
- Chọn mốc5 2 8 1 9 3 7 4 — lấy 4 làm pivot
- Đẩy hai phíaSố nhỏ hơn 4 dồn sang trái, lớn hơn dồn sang phải
- Đặt pivot2 1 3 · 4 · 5 8 9 7 — số 4 về đúng chỗ vĩnh viễn
- Làm tiếpLặp lại đúng như vậy cho hai phía, độc lập nhau
Nhanh nhờ đọc bộ nhớ liên tục
Phân hoạch quét mảng từ hai đầu vào giữa, nên CPU đọc gần như tuần tự và ít phải chờ. Cùng n log n với merge sort, nhưng không phải cấp phát và chép sang mảng phụ.
Trường hợp xấu nhất là n²
Chọn pivot ở phần tử đầu rồi gặp mảng đã sắp xếp sẵn: mỗi lần chia được một bên rỗng, một bên n-1. Thành n tầng thay vì log n tầng, tức là đúng n².
Thư viện thật không dùng quick sort thuần
C++, Go và Rust chạy introsort hoặc pdqsort: vẫn là quick sort, nhưng đếm độ sâu đệ quy và đổi sang heap sort khi quá sâu. Một cái lưới để n² không xảy ra.
Quick sort: được gì, mất gì
Ưu điểm
Nhanh nhất thực tế với mảng ngẫu nhiên
Tại chỗ, chỉ tốn log n cho ngăn xếp
Mặc định cho sắp xếp không ổn định
Nhược điểm
Xấu nhất O(n²) khi pivot chia lệch mọi lần
Không ổn định, phần tử bằng nhau có thể đảo
Đệ quy sâu có thể tràn ngăn xếp
Lưu lại để chạy tay sau
Loạt bài thuật toán sắp xếp cho dev Việt Nam.
