Thuật toán sắp xếp nhanh (Quick 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ề c&aacute;ch hoạt động của thuật to&aacute;n sắp xếp nhanh hay Quick Sort. Ngo&agrave;i ra, ta sẽ triển khai v&iacute; dụ về thuật to&aacute;n n&agrave;y bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <p style="text-align: justify;">Quicksort hay sắp xếp nhanh l&agrave; một thuật to&aacute;n dựa tr&ecirc;n c&aacute;ch tiếp cận chia để trị, trong đ&oacute; mảng được chia th&agrave;nh c&aacute;c mảng con v&agrave; c&aacute;c mảng con n&agrave;y được gọi một c&aacute;ch đệ quy để sắp xếp c&aacute;c phần tử.</p> <h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">1. C&aacute;ch thức hoạt động của thuật to&aacute;n QuickSort</h2> <ul> <li style="text-align: justify;">Bước 1: Một phần tử c&oacute; t&ecirc;n l&agrave; Pivot được chọn từ mảng. Ta c&oacute; thể chọn bất kỳ phần tử n&agrave;o trong mảng l&agrave;m phần tử n&agrave;y. Ở đ&acirc;y, ch&uacute;ng ta đ&atilde; sử dụng phần tử nằm ngo&agrave;i c&ugrave;ng ở b&ecirc;n phải (tức l&agrave; phần tử cuối c&ugrave;ng) của mảng l&agrave;m phần tử Pivot.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/ac955c64-4386-4238-9a86-884b641dcdbb" alt="thuat-toan-sap-xep-nhanh" /></p> <ul> <li>Bước 2: C&aacute;c phần tử nhỏ hơn phần tử Pivot sẽ được đặt ở b&ecirc;n tr&aacute;i v&agrave; c&aacute;c phần tử lớn hơn phần tử Pivot được đặt ở b&ecirc;n phải.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/b0c603b1-d685-4196-8b68-34f0d78bae3b" alt="thuat-toan-sap-xep-nhanh-2" /></p> <ul> <li style="text-align: justify;">C&aacute;ch sắp xếp như tr&ecirc;n c&oacute; thể c&oacute; được bằng c&aacute;c bước sau: <ul> <li style="text-align: justify;">Một con trỏ được cố định tại phần tử Pivot. Phần tử Pivot được so s&aacute;nh với c&aacute;c phần tử kh&aacute;c bắt đầu từ chỉ số đầu ti&ecirc;n. Nếu đạt đến phần tử lớn hơn phần tử Pivot, con trỏ thứ hai được đặt cho phần tử đ&oacute;.</li> <li style="text-align: justify;">B&acirc;y giờ, phần tử Pivot được so s&aacute;nh với c&aacute;c phần tử kh&aacute;c (con trỏ thứ ba). Nếu đạt đến phần tử nhỏ hơn phần tử Pivot, phần tử nhỏ hơn sẽ được ho&aacute;n đổi với phần tử lớn hơn được t&igrave;m thấy trước đ&oacute;.</li> </ul> </li> </ul> <p><img style="width: 100%;" src="../../../public_files/7059c880-aa5b-41a1-b1ec-a0242dab05e2" alt="thuat-toan-sap-xep-nhanh-3" /></p> <p><img style="width: 100%;" src="../../../public_files/978d989d-988d-456a-b1b3-cd705ece786e" alt="thuat-toan-sap-xep-nhanh-4" /></p> <p><img style="width: 100%;" src="../../../public_files/89dd6c3f-2ff9-4c14-970c-165f01a4e56f" alt="thuat-toan-sap-xep-nhanh-5" /></p> <p><img style="width: 100%;" src="../../../public_files/6220ae58-4985-4448-aee6-bc090ed4678e" alt="thuat-toan-sap-xep-nhanh-6" /></p> <p><img style="width: 100%;" src="../../../public_files/43e182e1-94d2-4b86-8604-0f5f7670c42c" alt="thuat-toan-sap-xep-nhanh-7" /></p> <ul> <li style="list-style-type: none;"> <ul> <li>Qu&aacute; tr&igrave;nh tiếp tục cho đến khi đạt được phần tử cuối c&ugrave;ng thứ hai.</li> <li>Cuối c&ugrave;ng, phần tử pivot được ho&aacute;n đổi với con trỏ thứ hai.</li> </ul> </li> </ul> <p><img style="width: 100%;" src="../../../public_files/a626875b-0ace-4024-a89c-2e7a92c9baee" alt="thuat-toan-sap-xep-nhanh-8" /></p> <ul> <li style="list-style-type: none;"> <ul> <li>B&acirc;y giờ c&aacute;c phần con b&ecirc;n tr&aacute;i v&agrave; b&ecirc;n phải của phần tử Pivot n&agrave;y được sử dụng để xử l&yacute; th&ecirc;m trong c&aacute;c bước b&ecirc;n dưới.</li> </ul> </li> <li>Bước 3: C&aacute;c phần tử Pivot được chọn lại một lần nữa cho c&aacute;c phần con b&ecirc;n tr&aacute;i v&agrave; b&ecirc;n phải ri&ecirc;ng biệt. Trong c&aacute;c phần con n&agrave;y, c&aacute;c phần tử Pivot được đặt ở đ&uacute;ng vị tr&iacute; của ch&uacute;ng. Sau đ&oacute;, bước 2 được lặp lại.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/cfc95677-d674-4a8d-97d8-fe6967ba59cb" alt="thuat-toan-sap-xep-nhanh-9" /></p> <ul> <li style="text-align: justify;">Bước 4: C&aacute;c phần con lại được chia th&agrave;nh c&aacute;c phần con nhỏ hơn cho đến khi mỗi phần con được tạo th&agrave;nh từ một phần tử duy nhất.</li> <li style="text-align: justify;">Bước 5: L&uacute;c n&agrave;y, mảng đ&atilde; được sắp xếp theo thứ tự.</li> </ul> <h3 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">2. Quicksort sử dụng đệ quy để sắp xếp c&aacute;c phần con</h3> <p style="text-align: justify;">Tr&ecirc;n cơ sở của c&aacute;ch tiếp cận chia để trị, thuật to&aacute;n Quick Sort c&oacute; thể được giải th&iacute;ch như sau:</p> <p style="text-align: justify;"><em>1. Bước chia</em></p> <p style="text-align: justify;">Mảng được chia th&agrave;nh c&aacute;c phần con v&agrave; lấy phần tử Pivot l&agrave;m điểm ph&acirc;n chia. C&aacute;c phần tử nhỏ hơn Pivot được đặt ở b&ecirc;n tr&aacute;i của n&oacute; v&agrave; c&aacute;c phần tử lớn hơn được đặt ở b&ecirc;n phải.</p> <p style="text-align: justify;"><em>2. Bước trị</em></p> <p style="text-align: justify;">C&aacute;c phần con b&ecirc;n tr&aacute;i v&agrave; b&ecirc;n phải lại được ph&acirc;n chia bằng c&aacute;ch chọn c&aacute;c phần tử Pivot cho ch&uacute;ng. Điều n&agrave;y c&oacute; thể đạt được bằng c&aacute;ch chuyển đệ quy c&aacute;c phần con v&agrave;o thuật to&aacute;n.</p> <p style="text-align: justify;"><em>3. Bước kết hợp</em></p> <p style="text-align: justify;">Bước n&agrave;y kh&ocirc;ng đ&oacute;ng một vai tr&ograve; quan trọng trong thuật to&aacute;n Quick sort n&agrave;y. Mảng đ&atilde; được sắp xếp ở cuối bước trị.</p> <p style="text-align: justify;">Ta c&oacute; thể hiểu c&aacute;ch thức hoạt động của thuật to&aacute;n Quick Sort với sự trợ gi&uacute;p của c&aacute;c h&igrave;nh minh họa b&ecirc;n dưới.</p> <p><img style="width: 100%;" src="../../../public_files/8eb20526-7834-45c0-a019-152912af66f9" alt="thuat-toan-sap-xep-nhanh-10" /></p> <p><img style="width: 100%;" src="../../../public_files/6442c7fc-fd54-418b-8429-43a8fb80fa94" alt="thuat-toan-sap-xep-nhanh-11" /></p> <h2 id="ftoc-heading-4" class="ftwp-heading">3. Thuật to&aacute;n sắp xếp nhanh</h2> <pre class="language-cpp"><code>H&agrave;m Quicksort với bộ tham số l&agrave; (Mảng, chỉ số b&ecirc;n tr&aacute;i cuối c&ugrave;ng, chỉ số b&ecirc;n phải cuối c&ugrave;ng) Nếu chỉ số b&ecirc;n tr&aacute;i cuối c&ugrave;ng &lt; chỉ số b&ecirc;n phải cuối c&ugrave;ng Thực hiện g&aacute;n cho chỉ số của phần tử Pivot &lt;- h&agrave;m ph&acirc;n chia(mảng,chỉ số b&ecirc;n tr&aacute;i cuối c&ugrave;ng, chỉ số b&ecirc;n phải cuối c&ugrave;ng) H&agrave;m QuickSort(mảng, chỉ số b&ecirc;n tr&aacute;i cuối c&ugrave;ng, chỉ số của phần tử Pivot) H&agrave;m QuickSort(mảng, chỉ số của phần tử Pivot + 1, chỉ số b&ecirc;n phải cuối c&ugrave;ng) H&agrave;m ph&acirc;n chia với bộ tham số l&agrave; (Mảng, chỉ số b&ecirc;n tr&aacute;i cuối c&ugrave;ng, chỉ số b&ecirc;n phải cuối c&ugrave;ng) Đặt chỉ số b&ecirc;n phải cuối c&ugrave;ng l&agrave;m chỉ số của phần tử Pivot Thực hiện g&aacute;n cho chỉ số lưu trữ &lt;- chỉ số b&ecirc;n tr&aacute;i cuối c&ugrave;ng - 1 Sử dụng v&ograve;ng lặp for với i = chỉ số b&ecirc;n tr&aacute;i cuối c&ugrave;ng + 1 cho đến chỉ số b&ecirc;n phải cuối c&ugrave;ng Nếu phần tử thứ i &lt; phần tử Pivot Ho&aacute;n đổi phần tử thứ i với phần tử tại chỉ số lưu trữ Tăng chỉ số lưu trữ l&ecirc;n 1 đơn vị Ho&aacute;n đổi phần tử Pivot với phần tử tại chỉ số lưu trữ + 1 Trả về chỉ số lưu trữ + 1</code></pre> <p>V&iacute; dụ: Triển khai thuật to&aacute;n Quicksort bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <pre class="language-cpp"><code>#include &lt;stdio.h&gt; void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } int divide(int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j &lt; high; j++) { if (arr[j] &lt;= pivot) { i++; swap(&amp;arr[i], &amp;arr[j]); } } swap(&amp;arr[i + 1], &amp;arr[high]); return (i + 1); } void sort(int arr[], int low, int high) { if (low &lt; high) { int pi = divide(arr, low, high); sort(arr, low, pi - 1); sort(arr, pi + 1, high); } } void print(int arr[], int size) { for (int i = 0; i &lt; size; ++i) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {10, 9, 4, 3, 2, 11, 8}; int n = sizeof(arr) / sizeof(arr[0]); sort(arr, 0, n - 1); printf("Mảng sau khi sắp xếp c&oacute; dạng l&agrave;: \n"); print(arr, n); }</code></pre> <p>Kết quả:</p> <div id="urvanov-syntax-highlighter-6107a6c2ed117512857150" class="urvanov-syntax-highlighter-syntax crayon-theme-classic urvanov-syntax-highlighter-font-monaco urvanov-syntax-highlighter-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover"> <div class="urvanov-syntax-highlighter-plain-wrap"> <pre class="language-cpp"><code>Mảng sau khi sắp xếp c&oacute; dạng l&agrave;: 2 3 4 8 9 10 11</code></pre> </div> <div class="urvanov-syntax-highlighter-main"> <h2 id="ftoc-heading-5" class="ftwp-heading" style="text-align: justify;">4. Độ phức tạp của thuật to&aacute;n sắp xếp nhanh</h2> <h3 style="text-align: justify;">4.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 xấu nhất: $O(n^2)$ <ul> <li>N&oacute; xảy ra khi phần tử Pivot được chọn l&agrave;m phần tử lớn nhất hoặc nhỏ nhất.</li> <li>Điều kiện n&agrave;y dẫn đến trường hợp phần tử Pivot nằm ở phần cuối c&ugrave;ng của mảng đ&atilde; sắp xếp. Một mảng con lu&ocirc;n trống rỗng v&agrave; một mảng con kh&aacute;c chứa n &ndash; 1 phần tử. Do đ&oacute;, quicksort chỉ được gọi tr&ecirc;n mảng con n&agrave;y.</li> <li>Tuy nhi&ecirc;n, thuật to&aacute;n sắp xếp nhanh c&oacute; hiệu suất tốt hơn cho c&aacute;c phần tử Pivot được ph&acirc;n bố đều.</li> </ul> </li> <li>Độ phức tạp của trường hợp tốt nhất: $O(n \times log n)$ <ul> <li>N&oacute; xảy ra khi phần tử Pivot lu&ocirc;n l&agrave;m phần tử ở giữa hoặc nằm gần phần tử giữa.</li> </ul> </li> <li>Độ phức tạp của trường hợp trung b&igrave;nh: $O(n \times log n)$ <ul> <li>N&oacute; xảy ra khi c&aacute;c điều kiện tr&ecirc;n kh&ocirc;ng xảy ra.</li> </ul> </li> </ul> <h3 style="text-align: justify;">4.2. Độ phức tạp về kh&ocirc;ng gian</h3> <p style="text-align: justify;">Độ phức tạp kh&ocirc;ng gian cho thuật to&aacute;n l&agrave; $O(O(log n))$</p> <h2 id="ftoc-heading-6" class="ftwp-heading" style="text-align: justify;">5. Ứng dụng của thuật to&aacute;n</h2> <p style="text-align: justify;">Quicksort được triển khai khi:</p> <ul style="text-align: justify;"> <li>Ng&ocirc;n ngữ lập tr&igrave;nh hoạt động tốt với kỹ thuật đệ quy.</li> <li>Độ phức tạp về thời gian đ&oacute;ng vai tr&ograve; quan trọng.</li> <li>Độ phức tạp về kh&ocirc;ng gian đ&oacute;ng vai tr&ograve; quan trọng.</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 nhanh hay Quick Sort. 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> </div> </div>