Ý tưởng
*Chia dãy cần sắp thành 2 phần
*Cách “chia”: ½ dãy bên trái chứa các giá trị nhỏ hơn ½ dãy bên phải
*Thực hiện việc sắp xếp trên từng dãy con (đệ qui)
Giải thuật
Cho dãy aL, aL+1, … aR
Bước 1:
Phân hoạch dãy aL … aR thành các dãy con:
*Dãy con 1: aL … aj< x
*Dãy con 2: aj+1 … ai-1 =x
*Dãy con 3: ai … aR > x
Bước 2:
*Nếu (L<j) Phân hoạch dãy aL … aj
*Nếu (i<R) Phân hoạch dãy ai … aR
Giải thuật phân hoạch dãy aL, aL+1, … aR thành 2 dãy con
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
x=a[k], i=L, j=R
Bước 2:
Phát hiện và hiệu chỉnh cặp a[i] và 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) Hoán vị a[i] và a[j]
Bước 3:
Nếu i<j: Lặp lại bước 2
Ngược lại: Dừng phân hoạch
Cài đặt
void QuickSort(int a[], int left, int right)
{ int i, j, x; x=a[(left+right)/2]; i=left, j=right;
do{ while(a[i]<x) i++;
while(a[j]>x) j--;
if(i<=j)
{
HoanVi(a[i], a[j]); i++; j--;
}
} while(i<j);
if(left<j) QuickSort(a, left, j);
if(i<right) QuickSort(a, i, right);
}