Thuật toán sắp xếp trộn (Merge Sort)

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về thuật to&aacute;n sắp xếp trộn hay Merge Sort. Ngo&agrave;i ra, ta sẽ triển khai v&iacute; dụ về c&aacute;ch l&agrave;m việc của thuật to&aacute;n n&agrave;y bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">1. Kh&aacute;i niệm</h2> <p style="text-align: justify;">Merge Sort hay thuật to&aacute;n sắp xếp trộn l&agrave; một trong những thuật to&aacute;n sắp xếp phổ biến nhất dựa tr&ecirc;n nguy&ecirc;n tắc của thuật to&aacute;n chia để trị. Ở đ&acirc;y, một b&agrave;i to&aacute;n được chia th&agrave;nh nhiều b&agrave;i to&aacute;n con. Mỗi vấn đề con được giải quyết một c&aacute;ch ri&ecirc;ng lẻ. Cuối c&ugrave;ng, c&aacute;c vấn đề con sẽ được kết hợp để tạo th&agrave;nh giải ph&aacute;p cuối c&ugrave;ng cho b&agrave;i to&aacute;n.</p> <p><img style="width: 100%;" src="../../../public_files/9429a6d0-555a-4733-872b-93559ba959ce" alt="thuat-toan-sap-xep-tron" /></p> <p><img style="width: 100%;" src="../../../public_files/ebed94c9-4a47-4ed5-8256-e1d1f5a92a05" alt="thuat-toan-sap-xep-tron-2" /></p> <h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">2. Chiến lược chia đ&ecirc;̉ trị</h2> <p style="text-align: justify;">Bằng c&aacute;ch sử dụng kỹ thuật chia để trị, ch&uacute;ng ta sẽ chia một vấn đề th&agrave;nh c&aacute;c b&agrave;i to&aacute;n con. Khi lời giải cho mỗi b&agrave;i to&aacute;n con đ&atilde; ho&agrave;n th&agrave;nh, ch&uacute;ng ta sẽ kết hợp kết quả từ c&aacute;c b&agrave;i to&aacute;n con để giải vấn đề ch&iacute;nh.</p> <p style="text-align: justify;">Giả sử ch&uacute;ng ta phải sắp xếp một mảng A. Một b&agrave;i to&aacute;n con sẽ l&agrave; sắp xếp một phần con của mảng n&agrave;y bắt đầu từ chỉ số p v&agrave; kết th&uacute;c tại chỉ số r, được k&yacute; hiệu l&agrave; A[p..r].</p> <p style="text-align: justify;"><em>1. Bước chia</em></p> <p style="text-align: justify;">Nếu q l&agrave; điểm giữa p v&agrave; r th&igrave; ta c&oacute; thể t&aacute;ch mảng con A[p..r] th&agrave;nh hai mảng A[p&hellip;q] v&agrave; A[q+1, r].</p> <p style="text-align: justify;"><em>2. Bước trị</em></p> <p style="text-align: justify;">Trong bước n&agrave;y, ch&uacute;ng ta sẽ cố gắng giải quyết c&aacute;c mảng con bằng c&aacute;ch sắp xếp cả hai mảng con A[p..q] v&agrave; A[q+1, r]. Nếu ch&uacute;ng ta chưa đến trường hợp cuối c&ugrave;ng, ch&uacute;ng ta sẽ chia cả hai mảng con n&agrave;y v&agrave; cố gắng sắp xếp ch&uacute;ng.</p> <p style="text-align: justify;"><em>3. Bước trộn</em></p> <p style="text-align: justify;">Khi bước trị kết th&uacute;c v&agrave; ch&uacute;ng ta nhận được hai mảng con được sắp xếp l&agrave; A[p&hellip;q] v&agrave; A[q+1, r] cho mảng A[p&hellip;r], ch&uacute;ng ta sẽ kết hợp c&aacute;c kết quả bằng c&aacute;ch tạo một mảng được sắp xếp A[p..r] từ hai mảng con đ&atilde; được sắp xếp A[p&hellip;q] v&agrave; A[q+1, r].</p> <h2 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">3. Thuật to&aacute;n Merge Sort</h2> <p style="text-align: justify;">H&agrave;m MergeSort sẽ chia mảng nhiều lần th&agrave;nh hai nửa cho đến khi ch&uacute;ng ta đến giai đoạn m&agrave; ch&uacute;ng ta cố gắng thực hiện thao t&aacute;c trộn tr&ecirc;n một mảng con c&oacute; k&iacute;ch thước bằng 1 tức l&agrave; p==r.</p> <p style="text-align: justify;">Sau đ&oacute;, h&agrave;m hợp nhất sẽ tiến h&agrave;nh triển khai v&agrave; kết hợp c&aacute;c mảng đ&atilde; sắp xếp th&agrave;nh c&aacute;c mảng lớn hơn cho đến khi to&agrave;n bộ mảng được hợp nhất.</p> <pre class="language-cpp"><code>H&agrave;m MergeSort với c&aacute;c tham số l&agrave; (A, p, r): Nếu p &gt; r Kết th&uacute;c h&agrave;m v&agrave; trả về q = (p+r)/2 MergeSort(A, p, q) MergeSort(A, q+1, r) Merge(A, p, q, r)</code></pre> <p style="text-align: justify;">Để sắp xếp to&agrave;n bộ một mảng, ch&uacute;ng ta cần gọi&nbsp;<span id="urvanov-syntax-highlighter-61077b6a27078331455607" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-e">MergeSort</span><span class="crayon-sy">(</span><span class="crayon-v">A</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">0</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-e">length</span><span class="crayon-sy">(</span><span class="crayon-v">A</span><span class="crayon-sy">)</span><span class="crayon-o">-</span><span class="crayon-cn">1</span><span class="crayon-sy">)</span></span></span>.</p> <p style="text-align: justify;">Như được biểu diễn trong h&igrave;nh b&ecirc;n dưới, thuật to&aacute;n sắp xếp trộn chia một mảng th&agrave;nh c&aacute;c mảng con cho đến khi ch&uacute;ng ta đạt được trường hợp cuối c&ugrave;ng l&agrave; mảng c&ograve;n c&oacute; 1 phần tử. Sau đ&oacute;, h&agrave;m hợp nhất chọn c&aacute;c mảng con đ&atilde; được sắp xếp v&agrave; hợp nhất ch&uacute;ng để sắp xếp dần to&agrave;n bộ mảng.</p> <p><img style="width: 100%;" src="../../../public_files/e57c66a6-27b2-4ece-8da5-8964e707f5ee" alt="thuat-toan-sap-xep-tron-3" /></p> <h2 id="ftoc-heading-4" class="ftwp-heading">4. Bước trộn của thuật to&aacute;n</h2> <p style="text-align: justify;">Mọi thuật to&aacute;n đệ quy đều phụ thuộc v&agrave;o trường hợp cơ sở v&agrave; khả năng kết hợp c&aacute;c kết quả từ c&aacute;c trường hợp cơ sở. Sắp xếp trộn cũng tương tự như vậy. Phần quan trọng nhất của thuật to&aacute;n sắp xếp trộn l&agrave; bước trộn.</p> <p style="text-align: justify;">Bước trộn l&agrave; bước hợp nhất hai danh s&aacute;ch đ&atilde; được sắp xếp (mảng) để x&acirc;y dựng một danh s&aacute;ch (mảng) đ&atilde; được sắp xếp lớn hơn. Thuật to&aacute;n duy tr&igrave; ba con trỏ, một con trỏ cho mỗi mảng trong số hai mảng v&agrave; một con trỏ để duy tr&igrave; chỉ số hiện tại của mảng được sắp xếp cuối c&ugrave;ng.</p> <pre class="language-cpp"><code>Ch&uacute;ng ta đ&atilde; đi đến phần cuối của bất kỳ mảng n&agrave;o hay chưa? Nếu chưa: Thực hiện so s&aacute;nh c&aacute;c phần tử hiện tại của cả hai mảng Sao ch&eacute;p phần tử nhỏ hơn v&agrave;o mảng đ&atilde; sắp xếp Di chuyển con trỏ của phần tử c&oacute; chứa phần tử nhỏ hơn Nếu c&oacute;: Sao ch&eacute;p tất cả c&aacute;c phần tử c&ograve;n lại của mảng kh&ocirc;ng rỗng.</code></pre> <h2 id="ftoc-heading-5" class="ftwp-heading">5. Viết đoạn m&atilde; cho thuật to&aacute;n</h2> <p style="text-align: justify;">Một sự kh&aacute;c biệt đ&aacute;ng ch&uacute; &yacute; giữa bước trộn m&agrave; ch&uacute;ng ta đ&atilde; m&ocirc; tả ở tr&ecirc;n v&agrave; bước ch&uacute;ng ta sử dụng để sắp xếp trộn l&agrave; ch&uacute;ng ta chỉ thực hiện h&agrave;m trộn tr&ecirc;n c&aacute;c mảng con li&ecirc;n tiếp.</p> <p style="text-align: justify;">Đ&acirc;y l&agrave; l&yacute; do tại sao ch&uacute;ng ta chỉ cần mảng, vị tr&iacute; đầu ti&ecirc;n, chỉ số cuối c&ugrave;ng của mảng con đầu ti&ecirc;n (ch&uacute;ng ta c&oacute; thể t&iacute;nh chỉ số đầu ti&ecirc;n của mảng con thứ hai) v&agrave; chỉ số cuối c&ugrave;ng của mảng con thứ hai.</p> <p style="text-align: justify;">Nhiệm vụ của ch&uacute;ng ta l&agrave; gộp hai mảng con A[p&hellip;q] v&agrave; A[q+1&hellip;r] để tạo ra một mảng đ&atilde; sắp xếp A[p&hellip;r]. V&igrave; vậy, c&aacute;c đầu v&agrave;o cho h&agrave;m l&agrave; A, p, q v&agrave; r</p> <p style="text-align: justify;">H&agrave;m trộn hoạt động như sau:</p> <ol> <li>Tạo bản sao của c&aacute;c mảng con $L \leftarrow A[p \cdots q]$ v&agrave; $M \leftarrow A[q + 1 \cdots r]$</li> <li>Tạo ba con trỏ $i, j$v&agrave; $k$ <ol> <li>i duy tr&igrave; chỉ số hiện tại của $L$ bắt đầu từ 1</li> <li>j duy tr&igrave; chỉ số hiện tại của $M$, bắt đầu từ 1</li> <li>k duy tr&igrave; chỉ số hiện tại của $A[q \cdots q]$, bắt đầu từ $p$</li> </ol> </li> <li>Cho đến khi ch&uacute;ng ta đến cuối L hoặc M, ta sẽ chọn phần tử lớn hơn trong số c&aacute;c phần tử từ L v&agrave; M v&agrave; đặt ch&uacute;ng v&agrave;o đ&uacute;ng vị tr&iacute; tại $A[p \cdots q]$</li> <li>Khi ch&uacute;ng ta hết c&aacute;c phần tử trong L hoặc M, ta sẽ chọn c&aacute;c phần tử c&ograve;n lại v&agrave; đưa v&agrave;o $A[p \cdots q]$</li> </ol> <h2 id="ftoc-heading-6" class="ftwp-heading">6. Giải th&iacute;ch từng bước về h&agrave;m trộn</h2> <p>Sẽ c&oacute; rất nhiều thứ xảy ra trong h&agrave;m n&agrave;y, v&igrave; vậy ch&uacute;ng ta sẽ lấy một v&iacute; dụ để xem n&oacute; sẽ hoạt động như thế n&agrave;o.</p> <p><img style="width: 100%;" src="../../../public_files/cdede4a6-d9c5-480e-b2cf-bfe9b66cabfd" alt="thuat-toan-sap-xep-tron-4" /></p> <p>Mảng&nbsp;<span id="urvanov-syntax-highlighter-61077b6a2707e239468108" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">A</span><span class="crayon-sy">[</span><span class="crayon-cn">0...5</span><span class="crayon-sy">]</span></span></span>&nbsp;chứa hai mảng con được sắp xếp&nbsp;<span id="urvanov-syntax-highlighter-61077b6a27081950126039" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">A</span><span class="crayon-sy">[</span><span class="crayon-cn">0...3</span><span class="crayon-sy">]</span></span></span>&nbsp;v&agrave;&nbsp;<span id="urvanov-syntax-highlighter-61077b6a27082409794743" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">A</span><span class="crayon-sy">[</span><span class="crayon-cn">4...5</span><span class="crayon-sy">]</span></span></span>.</p> <pre class="language-cpp"><code>void merge(int arr[], int p, int q, int r) { // Ở đ&acirc;y, p = 0, q = 4, r = 6 (K&iacute;ch thước của mảng)</code></pre> <p><em>Bước 1: Tạo bản sao ch&eacute;p của c&aacute;c mảng con đ&atilde; được sắp xếp</em></p> <pre class="language-cpp"><code>// Tạo L &larr; A [p..q] v&agrave; M &larr; A [q + 1..r] int n1 = q - p + 1 = 3 - 0 + 1 = 4; int n2 = r - q = 5 - 3 = 2; int L [4], M[2]; for (int i = 0; i &lt;4; i ++) L [i] = arr [p + i]; // L [0,1,2,3] = A [0,1,2,3] = [3, 7, 12, 14] for (int j = 0; j &lt;2; j ++) M [j] = arr [q + 1 + j]; // M [0,1,2,3] = A[4,5] = [8, 11]</code></pre> <p><img style="width: 100%;" src="../../../public_files/01ff14e9-7dbf-49a5-9be4-0659cb948fa0" alt="thuat-toan-sap-xep-tron-5" /></p> <p><em>Bước 2: Duy tr&igrave; chỉ số hiện tại của mảng con v&agrave; mảng ch&iacute;nh</em></p> <pre class="language-cpp"><code>int i, j, k; i = 0; j = 0; k = p;</code></pre> <p><img style="width: 100%;" src="../../../public_files/92c94026-5d9b-4e7f-a39b-1dfe56717336" alt="thuat-toan-sap-xep-tron-6" /></p> <p><em>Bước 3: Cho đến khi ch&uacute;ng ta đến cuối L hoặc M, ta sẽ chọn phần tử lớn hơn trong số L v&agrave; M v&agrave; đặt ch&uacute;ng v&agrave;o đ&uacute;ng vị tr&iacute; tại A[p&hellip;r]</em></p> <pre class="language-cpp"><code>while (i &lt; n1 &amp;&amp; j &lt; n2) { if (L[i] &lt;= M[j]) { arr[k] = L[i]; i++; } else { arr[k] = M[j]; j++; } k++; }</code></pre> <p><img style="width: 100%;" src="../../../public_files/e1916c75-24eb-443e-b27f-faf30d244055" alt="thuat-toan-sap-xep-tron-7" /></p> <p><img style="width: 100%;" src="../../../public_files/87686225-6a74-4b1c-8e8c-a3361332231f" alt="thuat-toan-sap-xep-tron-8" /></p> <p><img style="width: 100%;" src="../../../public_files/7a366950-e1fe-4052-abd5-6cab6aa8ad83" alt="thuat-toan-sap-xep-tron-9" /></p> <p><img style="width: 100%;" src="../../../public_files/99bd131e-c90c-4254-8d00-5db07f1ae871" alt="thuat-toan-sap-xep-tron-10" /></p> <p><img style="width: 100%;" src="../../../public_files/e6189907-5228-4c5d-8743-3cf6c5195e32" alt="thuat-toan-sap-xep-tron-11" /></p> <p style="text-align: justify;"><em>Bước 4: Khi ch&uacute;ng ta sử dụng hết c&aacute;c phần tử trong L hoặc M, ta sẽ chọn c&aacute;c phần tử c&ograve;n lại v&agrave; đưa v&agrave;o A[p&hellip;r]</em></p> <pre class="language-cpp"><code>// Ch&uacute;ng ta đ&atilde; tho&aacute;t khỏi v&ograve;ng lặp trước v&igrave; j &lt; n2 kh&ocirc;ng c&ograve;n đ&uacute;ng while (i &lt; n1){ arr[k] = L[i]; i++; k++; }</code></pre> <p><img style="width: 100%;" src="../../../public_files/dc624530-3397-4649-bdee-0eb13e11a732" alt="thuat-toan-sap-xep-tron-12" /></p> <p><img style="width: 100%;" src="../../../public_files/23873d23-864d-41d3-a6f8-daf425e67566" alt="thuat-toan-sap-xep-tron-13" /></p> <p><img style="width: 100%;" src="../../../public_files/80ba4231-fb8c-4dbe-a618-32a874b5f93d" alt="thuat-toan-sap-xep-tron-14" /></p> <pre class="language-cpp"><code>// Ch&uacute;ng ta đ&atilde; tho&aacute;t khỏi v&ograve;ng lặp trước v&igrave; j &lt; n1 kh&ocirc;ng c&ograve;n đ&uacute;ng while (j &lt; n2){ arr[k] = M[j]; j++; k++; }</code></pre> <p><img style="width: 100%;" src="../../../public_files/3d1170f1-7a19-4c29-bc27-8e256301f68f" alt="thuat-toan-sap-xep-tron-15" /></p> <p style="text-align: justify;">Bước n&agrave;y sẽ cần thiết nếu k&iacute;ch thước của M lớn hơn L. Khi kết th&uacute;c h&agrave;m trộn, mảng con A[p..r] cuối c&ugrave;ng cũng đ&atilde; được sắp xếp.</p> <p style="text-align: justify;">V&iacute; dụ: Triển khai sắp xếp trộn bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <pre class="language-cpp"><code>#include &lt;stdio.h&gt; void merge(int arr[], int p, int q, int r) { int n1 = q - p + 1; int n2 = r - q; int L[n1], M[n2]; for (int i = 0; i &lt; n1; i++) L[i] = arr[p + i]; for (int j = 0; j &lt; n2; j++) M[j] = arr[q + 1 + j]; int i, j, k; i = 0; j = 0; k = p; while (i &lt; n1 &amp;&amp; j &lt; n2) { if (L[i] &lt;= M[j]) { arr[k] = L[i]; i++; } else { arr[k] = M[j]; j++; } k++; } while (i &lt; n1) { arr[k] = L[i]; i++; k++; } while (j &lt; n2) { arr[k] = M[j]; j++; k++; } } void merge_sort(int arr[], int l, int r) { if (l &lt; r) { int m = l + (r - l) / 2; merge_sort(arr, l, m); merge_sort(arr, m + 1, r); merge(arr, l, m, r); } } void print(int arr[], int leng) { for (int i = 0; i &lt; leng; i++) printf("%d ", arr[i]); printf("\n"); } int main() { int arr[] = {8, 7, 14, 12, 11, 3}; int leng = sizeof(arr) / sizeof(arr[0]); merge_sort(arr, 0, leng - 1); printf("Mảng sau khi sắp xếp trộn l&agrave;: \n"); print(arr, leng); }</code></pre> <p>Kết quả:</p> <pre class="language-cpp"><code>Mảng sau khi sắp xếp trộn l&agrave;: 3 7 8 11 12 14</code></pre> <h2 id="ftoc-heading-7" class="ftwp-heading" style="text-align: justify;">7. Độ phức tạp của thuật to&aacute;n sắp xếp trộn</h2> <h3 style="text-align: justify;">7.1. Độ phức tạp về thời gian</h3> <ul style="text-align: justify;"> <li>Độ phức tạp của trường hợp tốt nhất: O(n * log n)</li> <li>Độ phức tạp của trường hợp xấu nhất: O(n * log n)</li> <li>Độ phức tạp của trường hợp trung b&igrave;nh: O(n * log n)</li> </ul> <h3 style="text-align: justify;">7.2. Độ phức tạp về kh&ocirc;ng gian</h3> <p style="text-align: justify;">Độ phức tạp kh&ocirc;ng gian của sắp xếp hợp nhất l&agrave; O(n).</p> <h2 id="ftoc-heading-8" class="ftwp-heading" style="text-align: justify;">8. Ứng dụng của thuật to&aacute;n sắp xếp trộn</h2> <ul style="text-align: justify;"> <li>Được sử dụng trong b&agrave;i to&aacute;n về đếm nghịch đảo.</li> <li>Sắp xếp một số lượng lớn dữ liệu m&agrave; kh&ocirc;ng thể lưu trữ hết trong bộ nhớ.</li> <li>Ứng dụng cho thương mại điện tử.</li> </ul> <p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về thuật to&aacute;n sắp xếp trộn. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n&nbsp;<a href="../../../">tek4</a>&nbsp;nh&eacute;!</p>