Thuật toán QUICKSORT

Ý 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); 

}