Thuat Toan QuickSort

Ý tưởng:

Đây là một phương pháp sắp xếp tốt do C.A.R Hoare đề xuất. Thuật toán này có
tốc độ trung bình nhanh hơn các thuật toán sắp xếp tổng quát khác. Do đó Hoare dùng
chữ “Quick” để đặt tên cho thuật toán này. Để sắp dãy a[1] ... a[n], ta thực hiện sắp xếp dãy a từ chỉ số 1 đến chỉ số n. QuickSort dựa trên phân hoạch dãy ban đầu thành hai phần dựa vào giá trị x, x là giá
trị của một phần tử tùy ý trong dãy ban đầu:
 Dãy thứ 1 : gồm các phần tử a[1]..a[i] có giá trị không lớn hơn x.
 Dãy thứ 2 : gồm các phần tử a[i]..a[n] có giá trị không nhỏ hơn x.
Sau khi phân hoạch thì dãy ban đầu được phân thành ba phần:
1. a[k] < x, với k = 1..i
2. a[k] = x, với k = i..j
3. a[k] > x, với k = j..n
Thuật toán :

 Bước 1 : Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc, left £ k £ right,
o Cho x = a[k], i = left, j = right.
 Bước 2 : Tìm và hoán vị cặp phần tử a[i] và a[j] không đúng thứ tự đang sắp.
o Bước 2-1 : Trong khi a[i] < x Þ i++;
o Bước 2-2 : Trong khi a[j] > x Þ j--;
o Bước 2-3 : Nếu i < j Þ Swap(a[i], a[j]) // a[i], a[j] sai thứ tự
 Bước 3 :
o Nếu i < j: Þ Bước 2; // chưa hết mảng dừng
o Nếu i ³ j: Þ Dừng.

Ví dụ : cho dãy : 6 , 5,  3 ,  1 ,  8 ,  7 ,  4

Ví dụ. Cho dãy: 1, 12, 5, 26, 7, 14, 3, 7, 2

Cài đặt:

void QuickSort(int a[], int left, int right)
{
int i, j;

int x;
x = a[(left+right)/2]; // chọn phần tử giữa làm gốc
i = left;
j = right;
do{
while (a[i] < x)
i++; // lặp đến khi a[i] >= x
while (a[j] > x)
j--; // lặp đến khi a[i] <= x
if ( i <= j) // nếu có 2 phần tử a[i] và a[j] ko theo thứ tự
{
Swap(a[i], a[j]);
i++; // qua phần tử kế tiếp
j--; // qua phần tử đứng trước
}
} while (i<j);
if (left < j) // phân hoạch đoạn bên trái
QuickSort(a, left, j);
if (right > i) // phân hoạch đoạn bên phải
QuickSort(a, i, right);
}