Hoạt động như thế nào?

Quick Sort thực hiện theo ba bước: chọn chốt, phân hoạch và đệ quy.

Quy trình từng bước:

1. Chọn chốt: chọn một phần tử làm chốt. Trong khóa học này, chúng ta luôn dùng phần tử cuối cùng.
2. Phân hoạch: duyệt qua các phần tử còn lại và chia chúng thành nhóm nhỏ hơn chốt và nhóm lớn hơn hoặc bằng chốt.
3. Đệ quy: sắp xếp nhóm nhỏ hơn và nhóm lớn hơn theo cùng cách, sau đó ghép chúng lại thành nhóm nhỏ hơn đã sắp xếp + chốt + nhóm lớn hơn đã sắp xếp.

Ví dụ với [7, 2, 9, 4]:

• Chốt là 4 (phần tử cuối cùng). Phân hoạch các phần tử còn lại [7, 2, 9]: các phần tử nhỏ hơn 4 là [2], các phần tử còn lại là [7, 9].
• Sắp xếp [2] (đã được sắp xếp) và sắp xếp [7, 9] (chốt là 9, kết quả là [7, 9]).
• Ghép lại: [2] + [4] + [7, 9] = [2, 4, 7, 9].