Chia Để Trị 2
Bài 6: Chia để trị (tiếp)
Trong bài này chúng ta sẽ áp dụng phương pháp chia để trị trong bài toán sắp xếp. Hai phương pháp sắp xếp đặc trưng dựa trên chia để trị là Quicksort và Merge Sort. Bài toán phát biểu như sau:
1. Quicksort
Quicksort được phát minh bởi Tony Hoare 1959. Quicksort là một thuật toán sắp xếp khá nhanh trong thực tế mặc dù trong trường hợp tồi nhất là $O(n^2)$. Phiên bản ngẫu nhiên của Quicksort có thời gian kì vọng là $O(n\log n)$, với hằng số đằng sau $O(.)$ khá nhỏ. Điều đó giải thich một phần vì sao Quicksort cũng hay được dùng trong thực tế.
Tư tưởng của quick sort khá đơn giản và gồm hai bước chính:
- Bước 1: chọn một phần tử của mảng (bất kì), $A[p]$, gọi là pivot, và phân mảng thành hai phần: phần 1 gồm những phần tử nhỏ hơn hoặc bằng $A[p]$ và phần 2 gồm những phần tử lớn hơn $A[p]$.
- Bước 2: gọi đệ quy sắp xếp phần 1 và phần 2
Dưới đây là giả mã của thuật toán. Hàm Partition($A[1,2,\ldots, n],p$) chia mảng $A$ thành hai phần với pivot được chọn là $A[p]$, và trả lại vị trí mới của $A[p]$ trong mảng sau khi đã chia.
if$(n > 1)$
Choose a pivot element $A[p]$
$r \leftarrow $ Partition($A[1,2,\ldots, n],p$)
QuickSort($A[1,2,\ldots, r-1]$)
QuickSort($A[r+1,2,\ldots, n]$)
Giả mã của thuật toán chia mảng với phân tử chọn (pivot) là $A[p]$, trả lại vị trí mới cuả phần tử có giá trị $A[p]$ trong mảng.
1. swap $A[p] \leftrightarrow A[n]$
2. $i \leftarrow 0$
3. $j \leftarrow n$
4. while $i$ < $j$
5. while $ A[i] < A[n]$
6. $i\leftarrow i+1$
7. while $ A[j] \geq A[n]$
8. $j\leftarrow j-1$
9. if $i< j$
10. swap $A[i] \leftrightarrow A[j]$
11. swap $A[i] \leftrightarrow A[n]$
12. return $i$
Ta sẽ xét kĩ hơn về thủ tục Partition($A[1,2,\ldots, n],p$). Dòng đầu tiên chỉ đơn giản đổi chỗ $A[p]$ với $A[n]$. (Lý do bạn sẽ thấy ngay sau đây.) Gọi $x$ là giá trị của $A[p]$ trước khi đổi chỗ với $A[n]$; $x = A[n]$ sau khi đổi chỗ. Mục tiêu của hai vòng lặp while (ở dòng 5 và 7) là tìm ra hai chỉ số $i_0$ và $j_0$ sao cho:
- Với mọi $i \leq i_0-1$, $A[i] < x$. Nói cách khác, $i_0$ là chỉ số nhỏ nhất sao cho $A[i_0] \geq x$.
- Với mọi $ j_0\geq j+1$, $A[j] \geq x$. Nói cách khác, $j_0$ là chỉ số nhỏ nhất sao cho $A[j_0] < x$. Đây cũng chính là lí do tại sao ta đổi chỗ $A[p]$ và $A[n]$ tại dòng đầu tiên.
Sau khi $i_0$ và $j_0$ đã tìm được, nếu $i_0 \geq j_0$ thì từ hai tính chất trên, ta suy ra: tất cả các phần tử của mảng con $A[1,\ldots, i_0-1]$ đều nhỏ hơn $x$, và tất cả các phần tử của mảng con $A[j_0+1,…, n]$ đều lớn hơn $x$. Chú ý, nếu $i_0 \geq j_0$ thì chỉ có trường hợp $i_0 = j_0 + 1$ là có thể xảy ra. Khi đó, đổi chỗ $A[i_0]$ và $A[n]$ (trong dòng 11 của thuật toán), và trả lại $i_0$ (dòng 12) là xong.
Nếu $i_0 < j_0$, ta có thể đổi chỗ $A[i_0]$ và $A[j_0]$ (dòng 10 của thuật toán). Hai tính chất của $i_0$ và $j_0$ phát biểu ở trên sẽ đảm bảo, sau khi đổi chỗ, $A[i_0] < x$ và $A[j_0] \geq x$, và thuật toán lúc này tiếp tục tìm kiếm $i_0$ và $j_0$ mới (vòng while ở dòng số 4.)
Ghi chú 1: Để hiểu kĩ đầu ra của hai vòng lặp while ở dòng 5 và 7, mình khuyến khích bạn đọc đưa ra ví dụ một mảng $A$ mà sau khi duyệt hai vòng này, $i_0 = j_0+1$.
Ghi chú 2: Sau khi đổi chỗ $i$ và $j$ ở dòng 10, ta có thể tăng luôn $i$ lên $1$ đơn vị và giảm $j$ đi 1 đơn vị. Làm như vậy ta sẽ tránh phải so sánh lại $A[i]$ và $A[j]$ với $A[n]$ trong lần duyệt vòng while tiếp theo ở dòng số 4. Câu hỏi cho bạn: nếu ta tăng $i$ lên $1$ sau khi đổi chỗ ở dòng 10, giá trị của $i$ có thể vượt quá $n$ không?
1.1 Tính đúng đắn của thuật toán
Để chứng minh tính đúng đắn của thuật toán, hay nói cách khác, chứng minh rằng đầu ra QuickSort($A[1,2,\ldots, n]$) là một mảng đã sắp xếp, ta chỉ cần chứng minh tính đúng đắn của thủ tục Partition($A[1,2,\ldots, n],p$). Tính đúng đắn của thủ tục này ta đã thảo luận ở trên. Do đó, bằng quy nạp, ta có thể chứng minh được thuật toán QuickSort($A[1,2,\ldots, n]$) là đúng.
1.2 Phân tích thời gian
Gọi $T(n)$ là thời gian của thuật toán Partition($A[1,2,\ldots, n],p$). Dễ thấy thủ tục Partition($A[1,2,\ldots, n],p$) chỉ mất thời gian $O(n)$ vì ta duyệt và so sánh mỗi phần tử của mảng $A$ với $A[n]$ tối đa 2 lần (xem ghi chú 2). Do đó, ta có công thức đệ quy:
$T(n) = T(r-1) + T(n-r) + O(n) \qquad (1)$
Ở đây $r$ phụ thuộc vào việc chọn phần tử pivot $A[p]$. Trong trường hợp tồi nhất, trong mỗi lần đệ quy, phần tử pivot chi mảng thành một phần có 1 phần tử và phần còn lại có n-2 phần tử. Như vậy phương trình (1) trở thành $T(n) = T(n-2) + O(n)$. Giải ra ta được $T(n) = O(n^2)$. Do đó, trong trường hợp tồi nhất, Quick Sort có thời gian chạy là $O(n^2)$.
Trong trường hợp lí tưởng, phần tử pivot chọn luôn chia mảng thành hai phần xấp xỉ như nhau. Khi đó phương trình (1) trở thành $T(n) = 2 T(n/2) + O(n)$. Sử dụng định lý thợ để giải phương trình này, ta suy ra $T(n) = O(n\log n)$.
2. Merge Sort
Merge Sort được phát minh bởi John von Neumann vào năm 1945. Đây là một thuật toán sắp xếp luôn đảm bảo thời gian chạy tồi nhất là $O(n\log n)$ dựa trên kĩ thuật chia để trị. Ý tưởng cơ bản của Merge Sort gồm hai bước:
- Bước 1: chia mảng thành hai phần với kích thước (xấp xỉ) bằng nhau, sau đó gọi đệ quy sắp xếp trên mỗi phần.
- Bước 2: trộn (merge) hai mảng con đã sắp xếp ở bước 1 thành mảng đã sắp xếp cho bước đệ quy hiện tại.
Dưới đây là giả mã của thuật toán. Hàm Merge($A[1,2,\ldots, n],m$) trộn hai mảng con $A[1,2,\ldots, m]$, $A[m+1,m+2, \ldots, n]$ đã sắp xếp thành mảng $A[1,2,\ldots,n]$ đã xắp xếp.
if$(n > 1)$
$m \leftarrow \lfloor n/2\rfloor$
MergeSort($A[1,2,\ldots, m]$)
MergeSort($A[m+1,2,\ldots, n]$)
Merge($A[1,2,\ldots, n],m$)
Giả mã của hàm Merge($A[1,2,\ldots, n],m$). Đầu vào của thủ tục này là mảng $A[1,2,\ldots, n]$ và chỉ số $m$, $1\leq m\leq n$, trong đó hai mảng con $A[1,\ldots, m]$ và $A[m+1,\ldots, n]$ đã được sắp xếp tăng dần. Chú ý, các phần tử của $A[1,\ldots, m]$ và của $A[m+1,\ldots, n]$ không có quan hệ gì đặc biệt với nhau cả. Ví dụ $A[1,5,6,2,3,7]$ với $m = 3$ là một đầu vào hợp lệ của thủ tục Merge.
1. $i \leftarrow 1; j \leftarrow m+1$
2. for $k \leftarrow 1$ to $n$
3. if $j > n$
4. $B[k] \leftarrow A[i]; i \leftarrow i + 1$
5. else if $i > m$
6. $B[k] \leftarrow A[j]; j \leftarrow j + 1$
7. else if $A[i] < A[j] $
8. $B[k] \leftarrow A[i]; i \leftarrow i + 1$
9. else
10. $B[k] \leftarrow A[j]; j \leftarrow j + 1$
11. for $k \leftarrow 1$ to $n$
12. $A[k] \leftarrow B[k]$
Ý tưởng của thủ tục Merge($A[1,2,\ldots, n],m$) khá đơn giản. Ta sử dụng một mảng phụ $B[1,\ldots,n]$ để hỗ trợ quá trình gộp: ta sẽ copy (dòng từ 2-10) các phần tử của $A$ sang $B$ sao cho sau khi quá trình copy hoàn tất, mảng $B$ sẽ được sắp xếp theo chiều tăng dần, và cuối cùng ta chỉ việc copy $B$ ngược trở lại mảng $A$ (dòng 11-12).
Để thực hiện copy, ta bắt đầu bằng hai con trỏ $i$ và $j$, trỏ tới hai phần tử đầu tiên của hai mảng con đã sắp xếp của $A$. Ta sẽ so sánh $A[i]$ với $A[j]$ (dòng số 7), nếu $A[i]$ nhỏ hơn $A[j]$ thì ta copy (dòng 8) $A[j]$ vào $B[k]$ – ô đang trống nhỏ nhất của $B$. Nên nhớ vì $A[j,\ldots, n]$ đã được sắp xếp theo chiều tăng dần, nếu $A[i] < A[j]$ thì nó nhỏ hơn mọi phần tử của mảng con $A[j,\ldots, n]$. Tương tự, nếu $A[i] \geq A[j]$, thì ta sẽ copy $A[j]$ vào $B[k]$ (dòng 10). Một khi $i$ hoặc $j$ đạt tới cuối mảng con tương ứng (dòng 3 và dòng 5 kiểm tra điều kiện này), thì ta chỉ việc copy phần còn lại của mảng con kia vào $B$ vì một mảng con đã được copy hoàn toàn sang $B$ rồi.
2.1 Tính đúng đắn của thuật toán.
Chứng minh tính đúng đắn của thuật toán, bằng phương pháp quy nạp, quy về chứng minh tính đúng đắn của thủ tục Merge($A[1,2,\ldots, n],m$). Tính đúng đắn của thủ tục gộp quy về chứng minh rằng mảng $B$ đã được sắp xếp tăng dần. Chi tiết hơn nữa, ta chỉ cần chứng minh (với $j$ ta chứng minh phát biểu tương tự):
Khi $A[i]$ được copy sang A[k] ở dòng 8, thì:
- $A[i]$ nhỏ hơn hoặc bằng tất cả các phần tử trong $A[j,\ldots, n]$.
- $A[i]$ nhỏ hơn hoặc bằng tất cả các phần tử trong $A[i+1,\ldots, m]$.
Đó là vì các phần tử của $B[k+1,\ldots, n]$ sau này là $A[i+1,\ldots, m] \cup A[j,\ldots, n]$. Tính chất (2) thì dễ thấy do $A[1,\ldots m]$ là một mảng đã sắp xếp; đây là điều kiện đầu vào của thủ tục gộp. Tính chất (1), như đã nói ở trên, là do $A[j,\ldots, n]$ cũng là một mảng đã sắp xếp, và dòng 8 chỉ xảy ra khi $A[i] < A[j]$.
2.2 Phân tích thời gian
Gọi $T(n)$ là thời gian của thuật toán. Không khó để thấy rằng Merge có thể thực hiện trong thời gian tuyến tính $O(n)$ vì thủ tục này chỉ duyệt qua mỗi phần tử của $A$ đúng một lần. Do đó, ta có công thức đệ quy:
$T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + O(n)$
Bỏ các dầu phần nguyên và sử dụng định lý thợ, ta thu được $T(n) = O(n\log n)$.
3. Tham khảo
[1] Jeff Erickson. Algorithm Lecture Notes, UIUC.
[2] Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001) [1990]. Introduction to Algorithms (2nd ed.) . MIT Press and McGraw-Hill. ISBN 0-262-03293-7
4. Bài tập
Bài 1: Gọi $i_0,j_0$ là giá trị đầu ra của hai biến $i,j$ sau khi thực hiện các dòng 5,6,7,8 của thủ tục Partition($A[1,2,\ldots, n],p$). Chứng minh rằng:
- Nếu $i_0 \geq j_0$ thì $i_0 = j_0 +1$.
- Giá trị $i_0$ không bao giờ lớn hơn $n$.
- Giá trị $j_0$ có thể bằng $0$.
Bài 2: Hoàn thành chứng minh tính đúng đắn của giải thuật Merge Sort bằng phương pháp quy nạp.
Bài 3: Thực thi cả hai thuật toán Quicksort và Merge Sort bằng ngôn ngữ C.
Bài 4*: Giả sử trong Quicksort, ta chọn $p$ là một số ngẫu nhiên trong tập ${1,2,\ldots, n}$. Gọi $X_{i,j}$ là sự kiện $A[i]$ và $A[j]$ sẽ được so sánh với nhau.
- Chứng minh rằng sự kiện $X_{i,j}$ xả ra với xác suất $\mathrm{Pr}[X_{i,j}] = \frac{2}{j-i+1}$.
- Đặt $I_{i,j} = 1$ nếu $X_{i,j}$ xảy ra và $I_{i,j} = 0$ nếu ngược lại. Chứng minh rằng kì vọng $E[I_{i,j}] = \mathrm{Pr}[X_{i,j}]$.
- Biết rằng số phép so sánh của thuật toán Quicksort, nếu tại mỗi bước đệ quy $p$ được chọn ngẫu nhiên, $E[T(n)] = \sum_{i=1}^n \sum_{j=i+1}^n E[I_{i,j}]$. Chứng minh rằng $E[T(n)] = O(n \log n)$.