Thuật toán dựa trên kỹ thuật chia để trị,được đề xuất bởi C.A.R Hoare
Ý tưởng như sau:
Sắp xếp dãy khóa k[1..n] thì có thể coi là sắp xếp đoạn từ chỉ số 1 tới chỉ số n trong dãy khóa đó.
Nếu đoạn đó có ít hơn 2 khóa thì không cần làm gì cả, nếu đoạn đó có ít nhất 2 khóa, ta chọn một khóa ngẫu nhiên nào đó làm chốt (pivot). Mọi khóa nhỏ hơn khóa chốt được xếp vào vị trí đứng trước chốt,mọi khóa lớn hơn chốt được xếp vào vị trí sau chốt.Sau phép hoán chuyển như vậy thì đoạn đang xét được chia làm 2 đoạn khác rỗng mà mọi khóa trong đoạn đầu đều <= chốt và mọi khóa trong đoạn sau đều >= chốt. Vấn đề trở thành sắp xếp 2 đoạn mới được tạo ra (độ dài ngắn hơn độ dài đoạn ban đầu) bằng phương pháp tương tự (gọi đệ quy)
Độ phức tạp là O(n*lgn) Continue reading
