Động lực

Quick Sort hoạt động bằng cách chọn một chốt và phân hoạch mảng quanh chốt đó: các giá trị nhỏ hơn nằm về một phía, các giá trị lớn hơn nằm về phía còn lại. Sau đó, mỗi phía được sắp xếp theo cùng một cách.

Tại sao nên học Quick Sort?

• Chạy nhanh trong thực tế: trung bình, thuật toán chạy trong thời gian O(n log n) và thường nhanh hơn các thuật toán sắp xếp O(n log n) khác.
• Được sử dụng rộng rãi: nhiều hàm sắp xếp trong thư viện chuẩn dựa trên Quick Sort hoặc một biến thể của thuật toán này.
• Chia để trị: thuật toán củng cố một khuôn mẫu được dùng trong nhiều thuật toán nâng cao.
• Chốt rất quan trọng: thuật toán cho thấy một lựa chọn thiết kế duy nhất (chốt) ảnh hưởng đến hiệu năng như thế nào, từ O(n log n) đến O(n²).