Tổng quan
Quick Sort là thuật toán chia-để-trị: chọn một 'pivot', phân hoạch mảng sao cho phần tử nhỏ hơn sang trái và lớn hơn sang phải, rồi sắp xếp đệ quy từng bên. Đây là thuật toán sắp xếp trong bộ nhớ mặc định của nhiều thư viện chuẩn.
Quick Sort hoạt động thế nào?
- Chọn một phần tử pivot trong đoạn hiện tại.
- Phân hoạch: sắp lại sao cho mọi giá trị nhỏ hơn pivot đứng trước và mọi giá trị lớn hơn đứng sau.
- Pivot lúc này đã ở đúng vị trí cuối cùng.
- Áp dụng đệ quy các bước trên cho đoạn con bên trái và bên phải.
Khi nào nên dùng?
- Sắp xếp trong bộ nhớ đa dụng, khi tốc độ trung bình là quan trọng nhất.
- Khi cần sắp tại chỗ — nó chỉ dùng O(log n) bộ nhớ ngăn xếp.
- Ưu tiên Merge Sort khi cần đảm bảo O(n log n) xấu nhất hoặc cần tính ổn định.
Phân tích độ phức tạp
Với phân hoạch cân bằng, Quick Sort chạy O(n log n) trung bình. Pivot tồi trên dữ liệu đã sắp có thể làm nó xuống O(n²); chọn pivot ngẫu nhiên hoặc trung vị-của-ba khiến điều đó hiếm xảy ra. Nó sắp tại chỗ và không ổn định.
Câu hỏi thường gặp
Vì sao Quick Sort có thể O(n²) ở trường hợp xấu nhất?
Nếu pivot luôn là phần tử nhỏ nhất hoặc lớn nhất, phân hoạch mất cân bằng tối đa (kích thước n−1 và 0), tạo ra n mức mỗi mức O(n). Chọn pivot ngẫu nhiên tránh được điều này trong thực tế.
Quick Sort hay Merge Sort — nên dùng cái nào?
Quick Sort thường nhanh hơn trong thực tế và sắp tại chỗ; Merge Sort đảm bảo O(n log n) và ổn định nhưng cần O(n) bộ nhớ phụ. Chọn theo yêu cầu về đảm bảo xấu nhất và tính ổn định.