[Thuật toán] Các thuật toán sắp xếp trong lập trình C - Thuật toán sắp xếp nhanh <Quick Sort>

1. 
   

1. Bài toán
   Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.
2. Ý tưởng
    - Ý tưởng của thuật toán này là "chia để trị", nói cách khác chúng ta tìm cách chia đôi dãy ban đầu bằng cách chọn ra một phần tử là chốt (pivot). Từ dãy ban đầu, tất cả phần tử nhỏ hơn phần tử chốt thì đưa về bên trái dãy, tất cả các phần tử lớn hơn hoặc bằng phần tử chốt thì đưa về bên phải dãy. Sau bước này ta có phần tử chốt là đứng đúng vị trí. Dãy ban đầu phân chia làm hai dãy con nằm hai bên chốt.
   - Tiếp tục phân chia các dãy con theo cách tương tự đến khi mọi dãy con đều có độ dài bằng 1.
   - Có thể lựa chọn phần tử chốt nằm đầu, cuối hay giữa dãy. Ở đây ta sẽ lựa chọn phần tử chốt nằm gần giữa dãy nhất.
3. Giải thuật
    a. Sắp xếp một đoạn bất kỳ X[L],...,X[R] với điều kiện L < R
        - Bước 1: pirot = (L+R) div 2, key=X[pirot]
        - Bước 2: i=L+1, j=R
        - Bước 3:
       * Nếu X[i] < key thì i=i+1;
       * Nếu X[j] > key thì j=j-1;
       - Bước 3: Nếu i>j thì đổi chổ X[i] với X[j], quay về Bước 3
      - Bước 4: Lặp lại từ Bước 1 đến Bước 3 với đoạn X[L],...,X[j-1] và X[j] đến X[R], dừng khi tất cả đoạn có độ dài là 1.

Thuật toán viết bằng C++ : 

Code:

void QuickSort(int X[], int n)
{
   Partition(1,n);
}

// hàm phân đoạn có 2 tham số L, R lần lượt là chỉ số đầu và cuối của //mảng
void Partition (int L, int R)
{
   if (L>=R) return;
       pirot=(L+R)div 2; // Luôn lấy chốt ở vị trí gần chính giữa dãy
   key = X[pirot];
   int i=L;
   int j= R;
   
   while (i<=j)
   {
      while (X[i] < key) i=i+1;
      while (X[j] > key) j=j-1;
      if (i<j)
      {
         swap(X[i],X[j]);
         i=i+1; j=j-1;      
      }      
   }
   Partition(L,j);
   Partition(i,R);   
}

4. Ví dụ
X = {7, 2, 5, 4, 1, 3, 8, 6}
Dãy ban đầu: 7, 2, 5, 4, 1, 3, 8, 6
Phân chia lần đầu:
Ban đầu ta có L=1, R=8, pirot=( 1+8 ) div 2 = 4, key=X[4]=4
i=1, j=8, tăng i trước, giảm j sau, ta chỉ xét tại các điểm có xẩy ra việc đổi chổ
i=1 < j=6, X[1]=7 > key > X[6]=3, swap(X[1],X[6], ta có 3, 2, 5, 4, 1, 7, 8, 6
i=3 < j=5, X[3]=5 > key > X[5]=1, swap(X[3],X[5], ta có 3, 2, 1, 4, 5, 7, 8, 6
i=5 > j=3, dừng việc xét, ta có 3, 2, 1, 4, 5, 7, 8, 6
Sau lần phân chia thứ nhất ta có hai dãy con nằm hai bên phần tử chốt {3, 2, 1} 4 {5, 7, 8, 6}
Thực hiện với dãy con {3, 2, 1}
L=1, R=3, pirot=( 1+3 ) div 2 = 2, key=X[2]=2
i=1 < j=3, X[1]=3 > key > X[3]=1, swap(X[1],X[3], ta có 1, 2, 3
i=3 > j=1, ngừng việc xét, ta có 1, 2, 3
Dãy này tiếp tục phân chia thành 2 dãy con {1},2, {3}, vì số phần tử trong các dãy đều bằng 1 nên ta không xét nữa.

Thực hiện với dãy con {5, 7, 8, 6}
L=i+1=5, R=8, pirot=( 4+8 ) div 2 = 6, key =X[6]=7
i=6 < j=8, X[6]=7 >= key > X[8]=6, swap(X[6],X[8], ta có 5, 6, 8, 7
i=7 > j= 6, dừng việc xét, ta có 5, 6, 8, 7
Dãy này lại phân làm hai dãy con {5} , 6, {8, 7}
Thực hiện tương tự với dãy {8, 7} ta có 7, {8}
Cuối cùng, ghép các dãy trên theo thứ tự ban đầu ta có 1, 2, 3, 4, 5, 6, 7, 8, dãy đã được sắp xếp.