Thuật toán sắp xếp chèn (Insertion 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 thuật to&aacute;n sắp xếp ch&egrave;n v&agrave; c&aacute;ch thức hoạt động của n&oacute;. Ngo&agrave;i ra, ta sẽ triển khai v&iacute; dụ về kiểu thuật to&aacute;n n&agrave;y được viết 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;">Thuật to&aacute;n sắp xếp ch&egrave;n hoạt động tương tự như ch&uacute;ng ta sắp xếp c&aacute;c l&aacute; b&agrave;i tr&ecirc;n tay trong một tr&ograve; chơi bằng c&aacute;ch sử dụng c&aacute;c l&aacute; b&agrave;i. Ch&uacute;ng ta giả định rằng l&aacute; b&agrave;i đầu ti&ecirc;n đ&atilde; được sắp xếp, ch&uacute;ng ta chọn một l&aacute; chưa được sắp xếp. Nếu l&aacute; chưa được sắp xếp lớn hơn l&aacute; tr&ecirc;n tay, n&oacute; được đặt ở b&ecirc;n phải, c&ograve;n nhỏ hơn sẽ l&agrave; b&ecirc;n tr&aacute;i. Theo c&aacute;ch tương tự, c&aacute;c l&aacute; chưa được ph&acirc;n loại kh&aacute;c được lấy v&agrave; đặt v&agrave;o đ&uacute;ng vị tr&iacute; của ch&uacute;ng.</p> <p style="text-align: justify;">Một c&aacute;ch tiếp cận tương tự được sử dụng bằng c&aacute;ch sắp xếp ch&egrave;n. Sắp xếp ch&egrave;n l&agrave; một thuật to&aacute;n sắp xếp c&oacute; nhiệm vụ đặt một phần tử chưa được sắp xếp v&agrave;o vị tr&iacute; th&iacute;ch hợp của n&oacute; trong mỗi lần lặp.</p> <h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">2. C&aacute;ch thức hoạt động của thuật to&aacute;n sắp xếp ch&egrave;n</h2> <ul> <li style="text-align: justify;">Giả sử ch&uacute;ng ta c&oacute; mảng như trong h&igrave;nh b&ecirc;n dưới v&agrave; cần sắp ch&uacute;ng theo thứ tự từ b&eacute; đến lớn.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/1ba4e9d2-41b5-4884-9159-8bedc17286a3" alt="thuat-toan-sap-xep-chen" /></p> <ul> <li style="text-align: justify;">Bước 1: Phần tử đầu ti&ecirc;n trong mảng được giả định l&agrave; đ&atilde; được sắp xếp. Ta sẽ lấy phần tử thứ hai v&agrave; lưu trữ ri&ecirc;ng trong kh&oacute;a. So s&aacute;nh kh&oacute;a với phần tử đầu ti&ecirc;n. Nếu phần tử đầu ti&ecirc;n lớn hơn kh&oacute;a, th&igrave; kh&oacute;a được đặt trước phần tử đầu ti&ecirc;n.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/1615aa15-dfaf-4848-a93f-d12ccc65d366" alt="thuat-toan-sap-xep-chen-2" /></p> <ul> <li style="text-align: justify;">Bước 2: B&acirc;y giờ, hai phần tử đầu ti&ecirc;n đ&atilde; được sắp xếp. Lấy phần tử thứ ba v&agrave; so s&aacute;nh n&oacute; với c&aacute;c phần tử b&ecirc;n tr&aacute;i của n&oacute;. Đặt n&oacute; ngay sau phần tử nhỏ hơn n&oacute;. Nếu kh&ocirc;ng c&oacute; phần tử n&agrave;o nhỏ hơn n&oacute;, th&igrave; ta sẽ đặt n&oacute; ở đầu mảng.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/e86f0e9d-4235-4614-bb55-9843899d3efc" alt="thuat-toan-sap-xep-chen-3" /></p> <ul> <li>Bước 3: Tương tự, ta sẽ đặt mọi phần tử chưa được sắp xếp v&agrave;o đ&uacute;ng vị tr&iacute; của n&oacute;</li> </ul> <p><img style="width: 100%;" src="../../../public_files/73554092-5211-4e2f-ae7e-6b6bc2ecc6e9" alt="thuat-toan-sap-xep-chen-4" /></p> <ul> <li>Cuối c&ugrave;ng, ta sẽ c&oacute; được mảng chứa c&aacute;c phần tử đ&atilde; được sắp xếp theo chiều tăng dần hay từ b&eacute; đến lớn.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/ed22211f-a2ae-4007-a67d-0ff576ddb03d" alt="thuat-toan-sap-xep-chen-5" /></p> <p>Đoạn giả m&atilde; cho thuật to&aacute;n sắp xếp ch&egrave;n như sau:</p> <pre class="language-cpp"><code>H&agrave;m sắp xếp ch&egrave;n với tham số đầu v&agrave;o l&agrave; mảng cần sắp xếp Đ&aacute;nh dấu phần tử đầu ti&ecirc;n l&agrave; đ&atilde; được sắp xếp Sử dụng v&ograve;ng lặp for cho mỗi phần tử chưa được sắp xếp x Lấy ra phần tử x Sử dụng v&ograve;ng lặp for với j = chỉ số của phần tử cuối c&ugrave;ng được sắp xếp tới gi&aacute; trị 0 Nếu phần tử hiện tại j &gt; x Di chuyển phần tử đ&atilde; sắp xếp sang b&ecirc;n cạnh từ tr&aacute;i qua phải Dừng v&ograve;ng lặp v&agrave; ch&egrave;n x v&agrave;o Kết th&uacute;c h&agrave;m sắp xếp</code></pre> <p>V&iacute; dụ: Triển khai thuật to&aacute;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 print(int arr[], int leng) { for (int i = 0; i &lt; leng; i++) { printf("%d ", arr[i]); } printf("\n"); } void sort(int arr[], int leng) { for (int step = 1; step &lt; leng; step++) { int key = arr[step]; int j = step - 1; while (key &lt; arr[j] &amp;&amp; j &gt;= 0) { arr[j + 1] = arr[j]; --j; } arr[j + 1] = key; } } int main() { int arr[] = {6, 1, 5, 8, 4}; int size = sizeof(arr) / sizeof(arr[0]); sort(arr, size); printf("Mảng sau khi sắp xếp l&agrave;:\n"); print(arr, size); }</code></pre> <p>Kết quả:</p> <pre class="language-cpp"><code>Mảng sau khi sắp xếp l&agrave;: 1 4 5 6 8</code></pre> <h2 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">3. Độ phức tạp của thuật to&aacute;n</h2> <h3 style="text-align: justify;">3.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>Giả sử, một mảng c&oacute; thứ tự tăng dần v&agrave; ta muốn sắp xếp n&oacute; theo thứ tự giảm dần. Trong trường hợp n&agrave;y, trường hợp xấu nhất sẽ xảy ra.</li> <li>Mỗi phần tử phải được so s&aacute;nh với mỗi phần tử kh&aacute;c, do đ&oacute;, đối với mỗi phần tử thứ n, (n-1) số ph&eacute;p so s&aacute;nh sẽ được thực hiện.</li> <li>Do đ&oacute;, tổng số ph&eacute;p so s&aacute;nh = $n \times (n - 1)n^2$</li> </ul> </li> <li>Độ phức tạp của trường hợp tốt nhất: $O(n)$ <ul> <li>Khi mảng đ&atilde; được sắp xếp, v&ograve;ng lặp b&ecirc;n ngo&agrave;i chạy trong n số lần trong khi v&ograve;ng lặp b&ecirc;n trong ho&agrave;n to&agrave;n kh&ocirc;ng chạy. V&igrave; vậy, chỉ c&oacute; n số ph&eacute;p so s&aacute;nh được thực hiện. Do đ&oacute;, độ phức tạp l&agrave; tuyến t&iacute;nh.</li> </ul> </li> <li>Độ phức tạp của trường hợp trung b&igrave;nh: $O(n)$ <ul> <li>Xảy ra khi c&aacute;c phần tử của một mảng c&oacute; thứ tự lộn xộn (kh&ocirc;ng tăng dần cũng kh&ocirc;ng giảm dần).</li> </ul> </li> </ul> <h3 style="text-align: justify;">3.2. Độ phức tạp về kh&ocirc;ng gian</h3> <p style="text-align: justify;">Độ phức tạp của kh&ocirc;ng gian l&agrave; $O(1)$ v&igrave; một biến phụ được sử dụng.</p> <h2 id="ftoc-heading-4" class="ftwp-heading" style="text-align: justify;">4. Ứng dụng của thuật to&aacute;n sắp xếp ch&egrave;n</h2> <p style="text-align: justify;">Sắp xếp ch&egrave;n được sử dụng khi:</p> <ul> <li style="text-align: justify;">Mảng c&oacute; một số lượng phần tử &iacute;t.</li> <li style="text-align: justify;">Chỉ c&oacute; một số phần tử được sắp xếp.</li> </ul> <p>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 ch&egrave;n hay Insertion 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>