Ý tưởng
Chọn x là giá trị của một phần tử tùy ý trong dãy ban đầu. Vị trí phần tử thường được chọn là k = (l + r)/2.
Thực hiện phân hoạch với x:
ak < x
k = 1..i
ak = x
k = i..j
ak > x
k = j..N
Dãy ban đầu được chia làm 3 phần, trong đó dãy con thứ 2 đã có thứ tự. Dãy ban đầu chỉ có thứ tự nếu dãy con 1 và 3 cũng có thứ tự. Nếu dãy con 1 và 3 chỉ có một phần tử thì chúng đã có thứ tự, ngược lại, ta lần lượt tiến hành phân hoạch từng dãy con theo phương pháp phân hoạch như trên.
Giải thuật phân hoạch
Bước 1: Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc, l ≤ k ≤ r
Bước 2: Phát hiện và hiệu chỉnh cặp phần tử a[i], a[j] nằm sai chỗ:
Bước 2a: Trong khi (a[i] < x) i++;
Bước 2b: Trong khi (a[j] > x) j--;
Bước 2c: Nếu i < j // a[i] ≥ x ≥ a[j] mà a[j] đứng sau a[i]
a[i] ↔ a[j];
Bước 3: Nếu i < j: Lặp lại bước 2. // chưa xét hết mảng
Nếu i ≥ j: Dừng
Giải thuật Quick Sort
Có thể phát biểu giải thuật sắp xếp Quick Sort một cách đệ qui như sau:
Bước 1: Phân hoạch dãy a1…ar thành các dãy con
Dãy con 1: a1..aj ≤ x
Dãy con 1: aj+1..ai-1 = x
Dãy con 1: ai..ar ≥ x
Bước 2: Nếu (l < j) // dãy con 1 có nhiều hơn một phần tử
Phân hoạch dãy a1..aj
Nếu (i < r) // dãy con 3 có nhiều hơn một phần tử
Phân hoạch dãy ai..ar