thuật toán quick sort - sắp xếp nhanh

Giải thuật QuickSort sắp xếp dãy a1, a2 ..., aN dựa trên việc phân hoạch dãy ban đầu thành 3 phần :

Phần 1: Gồm các phần tử  có giá trị bé hơn x
Phần 2: Gồm các phần tử  có giá trị bằng  x
Phần 3: Gồm các phần tử  có giá trị lớn hơn x
với x là giá trị của một phần tử  tùy ý trong dãy ban đầu.
Sau khi thực hiện phân hoạch, dãy ban đầu được phân thành 3 đoạn:
1. ak  ≤ x , với k = 1 .. j
2. ak  = x , với k =  j+1 .. i-1
3. ak   x , với k =  i..N



Đoạn thứ 2 đã có thứ tự.
Nếu các đoạn 1 và 3 chỉ có 1 phần tử  : đã có thứ tự
 khi đó dãy con ban đầu đã được sắp.
Đoạn thứ 2 đã có thứ tự.
Nếu các đoạn 1 và 3  có nhiều hơn 1 phần tử  thì dãy ban đầu chỉ có thứ tự khi các đoạn 1, 3 được sắp.
Để sắp xếp các đoạn 1 và 3, ta lần lượt tiến hành việc phân hoạch từng dãy con theo cùng phương pháp phân hoạch dãy ban đầu vừa trình bày …
Bước 1: Nếu left ≥ right //dãy có ít hơn 2 phần tử
Kết thúc; //dãy đã được sắp xếp
Bước 2: Phân hoạch dãy aleft … aright thành các đoạn: aleft.. aj, aj+1.. ai-1, ai.. aright
Đoạn 1  x
Đoạn 2: aj+1.. ai-1  = x
Đoạn 3: ai.. aright   x
Bước 3: Sắp xếp đoạn 1: aleft.. aj
Bước 4: Sắp xếp đoạn 3: ai.. aright


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 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 Swap(a[i],a[j]);
Bước 3 : Nếu  i < j: Lặp lại Bước 2.   Ngược lại: Dừng

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)
{ 
Swap(a[i],a[j]);
        i++ ; j--;
}
} while(i <= j);

if(left<j)
QuickSort(a, left, j);
if(i<right)
QuickSort(a, i, right);
}