<p>Ch&agrave;o mừng c&aacute;c bạn đến với kh&oacute;a học "Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật" tại TEK4.VN!</p>
<p>Bạn đ&atilde; bao giờ tự hỏi rằng để trở th&agrave;nh một lập tr&igrave;nh vi&ecirc;n xuất sắc, bạn cần những kiến thức v&agrave; kỹ năng g&igrave;? Kh&oacute;a học n&agrave;y ch&iacute;nh l&agrave; ch&igrave;a kh&oacute;a để mở ra c&aacute;nh cửa của tri thức đ&oacute;. Với nội dung phong ph&uacute; v&agrave; chi tiết, kh&oacute;a học Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật tại TEK4.VN hứa hẹn sẽ gi&uacute;p bạn x&acirc;y dựng nền tảng vững chắc v&agrave; th&agrave;nh thạo trong lập tr&igrave;nh.</p>
<p>Trong kh&oacute;a học n&agrave;y, ch&uacute;ng ta sẽ tập trung v&agrave;o việc kh&aacute;m ph&aacute; v&agrave; hiểu r&otilde; c&aacute;c cấu tr&uacute;c dữ liệu quan trọng như mảng, chuỗi k&yacute; tự, danh s&aacute;ch li&ecirc;n kết, ngăn xếp, h&agrave;ng đợi, bảng băm, tập hợp, c&acirc;y, đồ thị v&agrave; heap. C&aacute;c cấu tr&uacute;c dữ liệu n&agrave;y l&agrave; nền tảng của lập tr&igrave;nh, gi&uacute;p ch&uacute;ng ta giải quyết c&aacute;c vấn đề phức tạp một c&aacute;ch hiệu quả.</p>
<p>Kh&oacute;a học cũng sẽ gi&uacute;p bạn hiểu r&otilde; c&aacute;c thuật to&aacute;n cơ bản v&agrave; n&acirc;ng cao, bao gồm thuật to&aacute;n sắp xếp, thuật to&aacute;n t&igrave;m kiếm, thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n, thuật to&aacute;n t&igrave;m kiếm chuỗi k&yacute; tự, giải thuật tham lam, thuật to&aacute;n quay lui v&agrave; quy hoạch động. Bạn sẽ học c&aacute;ch &aacute;p dụng c&aacute;c thuật to&aacute;n n&agrave;y v&agrave;o c&aacute;c vấn đề thực tế, gi&uacute;p tăng cường kỹ năng giải quyết vấn đề của m&igrave;nh.</p>
<p>Ngo&agrave;i ra, ch&uacute;ng m&igrave;nh sẽ chia sẻ một số kinh nghiệm cần thiết cho buổi phỏng vấn, gi&uacute;p bạn chuẩn bị tốt nhất cho c&aacute;c cơ hội nghề nghiệp li&ecirc;n quan đến lập tr&igrave;nh trong tương lai. Bạn sẽ được học c&aacute;ch hiểu r&otilde; y&ecirc;u cầu của người phỏng vấn, thể hiện kỹ năng lập tr&igrave;nh của m&igrave;nh một c&aacute;ch hiệu quả v&agrave; trả lời c&aacute;c c&acirc;u hỏi một c&aacute;ch tr&ocirc;i chảy. Ch&uacute;ng m&igrave;nh tự tin rằng, sau khi bạn ho&agrave;n th&agrave;nh kh&oacute;a học n&agrave;y, bạn sẽ trở n&ecirc;n nhạy b&eacute;n trong tư duy lập tr&igrave;nh hiệu quả.</p>
<p>H&atilde;y tham gia kh&oacute;a học n&agrave;y để t&igrave;m hiểu s&acirc;u hơn về lập tr&igrave;nh v&agrave; mở rộng kỹ năng của bạn. TEK4.VN rất mong được hỗ trợ bạn trong qu&aacute; tr&igrave;nh học tập n&agrave;y.</p>

Cấu trúc dữ liệu và Giải thuật

<p style="text-align: justify;">Thuật to&aacute;n sắp xếp l&agrave; một trong những lớp thuật to&aacute;n v&agrave; thao t&aacute;c rất phổ biến trong c&aacute;c b&agrave;i to&aacute;n thực tế. Chẳng hạn như sắp xếp danh s&aacute;ch sinh vi&ecirc;n, sắp xếp c&aacute;c mặt h&agrave;ng để đề xuất theo thứ tự ưu ti&ecirc;n,...</p>
<p style="text-align: justify;">Trong b&agrave;i n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về một thuật to&aacute;n sắp xếp đơn giản v&agrave; trực quan nhất đầu ti&ecirc;n đ&oacute; l&agrave; thuật to&aacute;n sắp xếp nổi bọt.</p>
<h2 style="text-align: justify;">1. Kh&aacute;i niệm</h2>
<p style="text-align: justify;">Sắp xếp nổi bọt hay Bubble Sort l&agrave; một thuật to&aacute;n so s&aacute;nh c&aacute;c phần tử liền kề v&agrave; ho&aacute;n đổi vị tr&iacute; của ch&uacute;ng nếu ch&uacute;ng kh&ocirc;ng tu&acirc;n theo thứ tự được chỉ định. Thứ tự c&oacute; thể tăng dần hoặc giảm dần.</p>
<p style="text-align: justify;">C&aacute;ch thức hoạt động của thuật to&aacute;n:</p>
<ul style="text-align: justify;">
<li style="text-align: justify;">Bắt đầu từ chỉ số đầu ti&ecirc;n, ta sẽ so s&aacute;nh phần tử đầu ti&ecirc;n v&agrave; phần tử thứ hai. Nếu phần tử đầu ti&ecirc;n lớn hơn phần tử thứ hai, ch&uacute;ng sẽ được ho&aacute;n đổi.</li>
<li style="text-align: justify;">B&acirc;y giờ, ta sẽ so s&aacute;nh phần tử thứ hai v&agrave; phần tử thứ ba. Ho&agrave;n đổi ch&uacute;ng nếu ch&uacute;ng kh&ocirc;ng theo thứ tự.</li>
<li style="text-align: justify;">Qu&aacute; tr&igrave;nh tr&ecirc;n cứ tiếp tục cho đến phần tử cuối c&ugrave;ng.</li>
</ul>
<p><img style="width: 600px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/89b31238-7ce6-4a36-a04f-df6364251f18" alt="thuat-toan-sap-xep-noi-bot" /></p>
<ul style="text-align: justify;">
<li style="text-align: justify;">Qu&aacute; tr&igrave;nh tương tự diễn ra cho c&aacute;c lần lặp lại c&ograve;n lại. Sau mỗi lần lặp, phần tử lớn nhất trong số c&aacute;c phần tử chưa được sắp xếp sẽ được đặt ở cuối.</li>
<li style="text-align: justify;">Trong mỗi lần lặp, việc so s&aacute;nh diễn ra cho đến phần tử chưa được sắp xếp cuối c&ugrave;ng.</li>
<li style="text-align: justify;">Mảng được sắp xếp khi tất cả c&aacute;c phần tử chưa được sắp xếp được đặt đ&uacute;ng vị tr&iacute; của ch&uacute;ng.</li>
</ul>
<p><img style="width: 600px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/1bdff892-ae35-4da9-bcd0-6969b2c610e2" alt="thuat-toan-sap-xep-noi-bot-2" /></p>
<p><img style="width: 600px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/0d657b68-3068-4ec4-ad96-050730f26e5f" alt="thuat-toan-sap-xep-noi-bot-3" /></p>
<p><img style="width: 600px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/e996d7f2-cb12-4bdd-9778-25708e0d814e" alt="thuat-toan-sap-xep-noi-bot-4" /></p>
<p style="text-align: justify;">Thuật to&aacute;n của sắp xếp nổi bọt như sau:</p>
<pre class="language-c"><code>Bublesort (Mảng cần sắp xếp)
  Sử dụng v&ograve;ng lặp for với i = 1 cho tới chỉ số của phần tử chưa được sắp xếp cuối c&ugrave;ng -1
    Nếu phần tử b&ecirc;n tr&aacute;i &gt; phần tử b&ecirc;n phải
      Ho&aacute;n đổi hai phần tử n&agrave;y cho nhau
Kết th&uacute;c h&agrave;m</code></pre>
<p style="text-align: justify;">V&iacute; dụ: Triển khai sắp xếp nổi bọt bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p>
<div class="code-editor__wrapped code-editor__edit__wrapped" style="text-align: justify;" data-id="15995bbb-f3d7-4e3c-b63d-4496f5c78798">
<table class="code-editor__table" data-id="2766831c-4b20-469a-ad22-52bcef4e52e7">
<tbody>
<tr class="code-editor__edit__row__first">
<td colspan="2">RUN_CODE (*** ph&acirc;n biệt ***)</td>
</tr>
<tr>
<td>C</td>
<td>
<pre class="language-c" data-content="#include &lt;stdio.h&gt;
void sort(int arr[], int size) {
  for (int step = 0; step &lt; size - 1; ++step) {
    for (int i = 0; i &lt; size - step - 1; ++i) {
      if (arr[i] &gt; arr[i + 1]) {
        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
  }
}

void print(int arr[], int size) {
  for (int i = 0; i &lt; size; ++i) {
    printf(" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>#include &lt;stdio.h&gt;
void sort(int arr[], int size) {
  for (int step = 0; step &lt; size - 1; ++step) {
    for (int i = 0; i &lt; size - step - 1; ++i) {
      if (arr[i] &gt; arr[i + 1]) {
        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
  }
}

void print(int arr[], int size) {
  for (int i = 0; i &lt; size; ++i) {
    printf("%d  ", arr[i]);
  }
  printf("\n");
}
int main() {
  int arr[] = {4, 7, 5, 6, 0};
  int size = sizeof(arr) / sizeof(arr[0]);
  sort(arr, size);
  printf("Mảng sau khi sắp xếp c&oacute; dạng như sau:\n");
  print(arr, size);
}</code></pre>
</td>
</tr>
</tbody>
</table>
</div>
<p style="text-align: justify;">Kết quả:</p>
<pre class="language-cpp"><code>Mảng sau khi sắp xếp c&oacute; dạng như sau:
0  4  5  6  7</code></pre>
<h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">2. Thuật to&aacute;n sắp xếp nổi bọt tối ưu</h2>
<p style="text-align: justify;">Trong đoạn m&atilde; tr&ecirc;n, tất cả c&aacute;c ph&eacute;p so s&aacute;nh c&oacute; thể được thực hiện ngay cả khi mảng đ&atilde; được sắp xếp sẵn đ&uacute;ng thứ tự. Điều n&agrave;y l&agrave;m tăng thời gian thực hiện kh&ocirc;ng đ&aacute;ng c&oacute;. Ch&uacute;ng ta c&oacute; thể tối ưu đoạn m&atilde; tr&ecirc;n bằng c&aacute;ch sử dụng một biến bổ sung l&agrave; <code>swapped</code> để ghi lại trạng th&aacute;i của mảng c&oacute; bị thay đổi hay kh&ocirc;ng. Sau mỗi lần lặp, nếu kh&ocirc;ng c&oacute; sự ho&aacute;n đổi n&agrave;o diễn ra th&igrave; hiển nhi&ecirc;n ta kh&ocirc;ng cần thực hiện th&ecirc;m c&aacute;c v&ograve;ng lặp nữa.</p>
<p style="text-align: justify;">Trong trường hợp n&agrave;y, biến <code>swapped</code> được g&aacute;n gi&aacute; trị khởi tạo l&agrave; <code>false</code>. Nếu sau v&ograve;ng lặp m&agrave; biến n&agrave;y vẫn c&oacute; gi&aacute; trị l&agrave; <code>false</code>, ch&uacute;ng ta c&oacute; thể bỏ qua c&aacute;c v&ograve;ng lặp tiếp theo.</p>
<p style="text-align: justify;">Thuật to&aacute;n để sắp xếp nổi bọt được tối ưu h&oacute;a c&oacute; dạng như sau:</p>
<pre class="language-c"><code>BubleSort (Mảng cần sắp xếp)
  G&aacute;n gi&aacute; trị false cho biến swapped
  Sử dụng v&ograve;ng lặp for với i = 1 cho đến chỉ số của phần tử cuối c&ugrave;ng chưa được sắp xếp - 1
    if phần tử b&ecirc;n tr&aacute;i &gt; phần tử b&ecirc;n phải
      Ho&aacute;n đổi vị tr&iacute; của hai phần tử
      G&aacute;n true cho biến swapped
    if swapped = false tho&aacute;t khỏi h&agrave;m
Kết th&uacute;c h&agrave;m</code></pre>
<p style="text-align: justify;">V&iacute; dụ:</p>
<div class="code-editor__wrapped code-editor__edit__wrapped" style="text-align: justify;" data-id="dfcb94d4-9924-440c-ac44-26901098edf3">
<table class="code-editor__table" data-id="cb8a6280-fcce-4c90-9d62-49e283040e87">
<tbody>
<tr class="code-editor__edit__row__first">
<td colspan="2">RUN_CODE (*** ph&acirc;n biệt ***)</td>
</tr>
<tr>
<td>C</td>
<td>
<pre class="language-c" data-content="#include &lt;stdio.h&gt;

void sort(int arr[], int size) {
  for (int step = 0; step &lt; size - 1; ++step) {
    int swapped = 0;
    for (int i = 0; i &lt; size - step - 1; ++i) {
      if (arr[i] &gt; arr[i + 1]) {
        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        swapped = 1;
      }
    }
    if (swapped == 0)
      break;
  }
}
void print(int arr[], int size) {
  for (int i = 0; i &lt; size; ++i) {
    printf(" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>#include &lt;stdio.h&gt;

void sort(int arr[], int size) {
  for (int step = 0; step &lt; size - 1; ++step) {
    int swapped = 0;
    for (int i = 0; i &lt; size - step - 1; ++i) {
      if (arr[i] &gt; arr[i + 1]) {
        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        swapped = 1;
      }
    }
    if (swapped == 0)
      break;
  }
}
void print(int arr[], int size) {
  for (int i = 0; i &lt; size; ++i) {
    printf("%d  ", arr[i]);
  }
  printf("\n");
}
int main() {
  int arr[] = {4, 7, 5, 6, 0};
  int size = sizeof(arr) / sizeof(arr[0]);
  sort(arr, size);
  printf("Mảng sau khi được sắp xếp c&oacute; dạng như sau:\n");
  print(arr, size);
}</code></pre>
</td>
</tr>
</tbody>
</table>
</div>
<p style="text-align: justify;">Kết quả:</p>
<pre class="language-cpp"><code>Mảng sau khi được sắp xếp c&oacute; dạng như sau:
0  4  5  6  7</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>
<p style="text-align: justify;">Sắp xếp nổi bọt l&agrave; một trong những thuật to&aacute;n sắp xếp đơn giản nhất. C&oacute; hai v&ograve;ng lặp được thực hiện trong thuật to&aacute;n. Mỗi v&ograve;ng lặp ngo&agrave;i sẽ thực hiện c&aacute;c thao t&aacute;c lặp giảm dần trong v&ograve;ng lặp b&ecirc;n trong.</p>
<table style="border-collapse: collapse; width: 21.2649%; height: 241px; margin-left: auto; margin-right: auto;" border="1">
<tbody>
<tr>
<td style="width: 39.7943%; text-align: center;">V&ograve;ng lặp</td>
<td style="width: 60.1266%; text-align: center;">Số lần so s&aacute;nh</td>
</tr>
<tr>
<td style="width: 39.7943%; text-align: center;">Lần 1</td>
<td style="width: 60.1266%; text-align: center;">(n-1)</td>
</tr>
<tr>
<td style="width: 39.7943%; text-align: center;">Lần 2</td>
<td style="width: 60.1266%; text-align: center;">(n-2)</td>
</tr>
<tr>
<td style="width: 39.7943%; text-align: center;">Lần 3</td>
<td style="width: 60.1266%; text-align: center;">(n-3)</td>
</tr>
<tr>
<td style="width: 39.7943%; text-align: center;">&hellip;&hellip;.</td>
<td style="width: 60.1266%; text-align: center;">&hellip;&hellip;</td>
</tr>
<tr>
<td style="width: 39.7943%; text-align: center;">Lần cuối</td>
<td style="width: 60.1266%; text-align: center;">1</td>
</tr>
</tbody>
</table>
<p style="text-align: justify;">Số ph&eacute;p so s&aacute;nh: $(n - 1) + (n - 2) + (n - 3) + \cdots + 1 = \frac{n(n - 1)}{2}$ gần bằng $n^2$</p>
<p style="text-align: justify;">Độ phức tạp: $O(n^2)$</p>
<p style="text-align: justify;">Ngo&agrave;i ra, ch&uacute;ng ta c&oacute; thể ph&acirc;n t&iacute;ch độ phức tạp bằng c&aacute;ch quan s&aacute;t số v&ograve;ng lặp. C&oacute; 2 v&ograve;ng lặp <code>for</code> n&ecirc;n độ phức tạp l&agrave; $n \times n = n^2$</p>
<ul style="text-align: justify;">
<li>Độ phức tạp của trường hợp xấu nhất: $O(n^2)$. Nếu ch&uacute;ng ta muốn sắp xếp theo thứ tự tăng dần v&agrave; mảng theo thứ tự giảm dần th&igrave; trường hợp xấu nhất sẽ xảy ra.</li>
<li>Độ phức tạp của trường hợp tốt nhất: $O(n)$. Nếu mảng đ&atilde; được sắp xếp, th&igrave; kh&ocirc;ng cần sắp xếp.</li>
<li>Độ phức tạp của trường hợp trung b&igrave;nh: $O(n^2)$. N&oacute; xảy ra khi c&aacute;c phần tử của 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>
<p style="text-align: justify;">Độ phức tạp của kh&ocirc;ng gian lưu trữ của thuật to&aacute;n l&agrave; $O(1)$ v&igrave; ch&uacute;ng ta sử dụng một biến trung gian bổ sung để thực hiện việc ho&aacute;n đổi. Trong phi&ecirc;n bản tối ưu hơn của thuật to&aacute;n, ch&uacute;ng ta sử dụng th&ecirc;m một biến swapped l&agrave;m tăng th&ecirc;m độ phức tạp của kh&ocirc;ng gian, do đ&oacute; độ phức tạp kh&ocirc;ng gian trong trường hợp n&agrave;y l&agrave; $O(2)$.</p>
<h2 id="ftoc-heading-4" class="ftwp-heading" style="text-align: justify;">4. Ứng dụng của thuật to&aacute;n Bubble Sort</h2>
<p style="text-align: justify;">Bubble Sort được sử dụng trong c&aacute;c trường hợp sau đ&acirc;y:</p>
<ul style="text-align: justify;">
<li>Độ phức tạp của đoạn m&atilde; kh&ocirc;ng quan trọng.</li>
<li>Ưu ti&ecirc;n c&aacute;c đoạn m&atilde; ngắn.</li>
</ul>
<p style="text-align: justify;">X&eacute;t về độ phức tạp t&iacute;nh to&aacute;n th&igrave; Bubble Sort l&agrave; thuật to&aacute;n sắp xếp c&oacute; độ phức tạp lớn v&agrave; do đ&oacute; kh&ocirc;ng tối ưu để sử dụng nếu cần thực thi với hiệu năng cao hoặc với một lượng rất lớn dữ liệu v&igrave; khi đ&oacute; n&oacute; sẽ thực hiện tương đối chậm.</p>
<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 nổi bọt. Chắc hẳn đến đ&acirc;y bạn đ&atilde; hiểu r&otilde; hơn về thuật to&aacute;n n&agrave;y rồi chứ? N&agrave;o, h&atilde;y thử sức với b&agrave;i tập được y&ecirc;u cầu sau đ&acirc;y nh&eacute;.</p>
<h2 style="text-align: justify;">5. B&agrave;i tập &aacute;p dụng</h2>
<h3>Y&ecirc;u cầu b&agrave;i tập</h3>
<p>H&atilde;y viết chương tr&igrave;nh thực thi thuật to&aacute;n Bubble Sort (sắp xếp nổi bọt) đ&atilde; được tr&igrave;nh b&agrave;y ở trong nội dung b&agrave;i học để thực hiện sắp xếp một d&atilde;y số nguy&ecirc;n được nhập v&agrave;o từ b&agrave;n ph&iacute;m theo thứ tự tăng dần.</p>
<h4>Định dạng đầu v&agrave;o</h4>
<p>Đầu v&agrave;o được nhập tr&ecirc;n hai d&ograve;ng:</p>
<ul>
<li>D&ograve;ng đầu ti&ecirc;n l&agrave; số <code>n</code> thể hiện số lượng phần tử của d&atilde;y số nguy&ecirc;n.</li>
<li>D&ograve;ng thứ hai l&agrave; c&aacute;c số nguy&ecirc;n <code>a[i]</code> tương ứng theo thứ tự của d&atilde;y được nhập v&agrave;o từ b&agrave;n ph&iacute;m được ph&acirc;n t&aacute;ch nhau bởi một dấu c&aacute;ch.</li>
</ul>
<h4>Định dạng đầu ra</h4>
<p>Đầu ra được in ra tr&ecirc;n một d&ograve;ng d&atilde;y số đ&atilde; được sắp xếp, trong đ&oacute; sau mỗi số c&oacute; một dấu c&aacute;ch.</p>
<h3>V&iacute; dụ</h3>
<p>Đầu v&agrave;o 1:</p>
<pre class="language-c" data-content="5%0A1%202%204%203%205" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>5
1 2 4 3 5</code></pre>
<p>Đầu ra 1:</p>
<pre class="language-c" data-content="1%202%203%204%205%20" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>1 2 3 4 5 </code></pre>
<p>[___NOTE_H&atilde;y lưu &yacute; dấu c&aacute;ch đằng sau số 5. Sau mỗi phần tử được in ra đều c&oacute; một dấu c&aacute;ch._NOTE___]</p>
<p>Đầu v&agrave;o 2:</p>
<pre class="language-c" data-content="10%0A0%201%202%203%204%205%206%207%208%209" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>10
0 1 2 3 4 5 6 7 8 9</code></pre>
<p>Đầu ra 2:</p>
<pre class="language-c" data-content="0%201%202%203%204%205%206%207%208%209%20" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>0 1 2 3 4 5 6 7 8 9 </code></pre>
<h3>Điều kiện r&agrave;ng buộc</h3>
<ul>
<li>$0 \leq n \leq 10^3$</li>
<li>-10^3 \leq a[i] \leq 10^3$.</li>
</ul>