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.
- Ý 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
- 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.
4. Mã thực thi C
void QuickSort(int iArray[], int left, int right)
{
if (left >= right) return;
int iMid = (left + right) / 2, iLeft= left, iRight = right;
int iX = iArray[iMid]; //Lấy Mid là mốc
while (iLeft <= iRight)
{
while (iArray[iLeft] < iX) iLeft++;
while (iArray[iRight] > iX) iRight--;
if (iLeft <= iRight)
{
Swap(iArray[iLeft], iArray[iRight]);
iLeft++; iRight--;
}
}
}
5. Ví dụ
X = {7, 2, 5, 4, 1, 3, 8, 6}
Dãy ban đầu: 7, 2, 5, 4, 1, 3, 8, 6
1. 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}
2. 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.
3. 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}
4. 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.
6.Đánh giá giải thuật
Hiệu quả thực hiện của giải thuật Quick Sort phụ thuộc vào việc chọn giá trị mốc. Trường hợp tốt nhất xảy giả nếu mỗi lần phân hoạch đều chọn được phần tử median (phần tử lớn hơn hoặc bằng nữa số phần tử, và nhỏ hơn hoặc bằng nữa số phần tử còn lại) làm mốc, khi đó dãy được phân chia thành 2 phần bằng nhau và cần log2(n) lần phân hoạch thì sắp xếp xong. Nhưng nếu mỗi lần phân hoạch lại chọn nhầm phần tử có giá trị cực đại (hay cực tiểu) làm mốc, dãy sẽ bị phân chia thành 2 phần không đều: một phần chỉ có 1 phần tử, phần còn lại gồm n-1 phần tử, do vậy cần phân hoạch n lần mới sắp xếp xong.
Thống kê độ phức tạp:
Tốt nhất: n*log2(n)
Trung bình: n*log2(n)
Xấu nhất: n^2
Các thuật toán sắp xếp khác:
[Thuật toán đang xem] Quick Sort
0 nhận xét:
Đăng nhận xét