Trong phần n&agrave;y, ch&uacute;ng ta sẽ thực hiện thuật to&aacute;n sắp xếp tập hợp kiểu List bằng c&aacute;ch sử dụng thuật to&aacute;n sắp xếp nổi bọt. Trước hết, ch&uacute;ng ta sẽ c&ugrave;ng t&igrave;m hiểu về thuật to&aacute;n n&agrave;y nh&eacute;.
<h2 style="text-align: justify;">1. C&aacute;ch thức hoạt động của thuật to&aacute;n</h2>
<ul style="text-align: justify;">
<li>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>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>Qu&aacute; tr&igrave;nh tr&ecirc;n được thực hiện tiếp tục cho đến phần tử cuối c&ugrave;ng.</li>
</ul>
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/aa8774bd-9592-4626-9c95-bd87cf94708b" alt="sap-xep-noi-bot-python-1" />
<ul style="text-align: justify;">
<li>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>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>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>
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/b0b3887f-9d73-4102-b340-59f515261888" alt="sap-xep-noi-bot-python-2" />
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/4bb44eb4-d1d9-4bc7-825e-d25829e194c3" alt="sap-xep-noi-bot-python-3" />
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/dd3679c4-8527-42c2-8c2a-7ba56ff50fa8" alt="sap-xep-noi-bot-python-4" />
<h2 style="text-align: justify;"> 2. Viết đoạn m&atilde; thực thi</h2>
Đoạn m&atilde; thực thi như sau:
<pre class="line-numbers language-python" tabindex="0"><code>def bubbleSort(arr):
 n = len(arr)
 #Duyệt qua tất cả c&aacute;c phần tử
 for i in range(n-1):
 for j in range(0, n-i-1):
 #Ho&aacute;n đổi phần tử nếu n&oacute; lớn hơn phần tử sau n&oacute;
 if arr[j] &gt; arr[j + 1] :
 arr[j], arr[j + 1] = arr[j + 1], arr[j]

#Thực thi đoạn m&atilde;
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
for i in range(len(arr)):
 print("%d" % arr[i], end=" ")</code></pre>
Kết quả đầu ra:
<img style="width: 100%;" src="http://tek4vn.2soft.top/public_files/a-png-58" alt="a" />
Trong đoạn m&atilde; b&ecirc;n tr&ecirc;n, ch&uacute;ng ta thực hiện định nghĩa cho một h&agrave;m c&oacute; nhiệm vụ l&agrave; thực hiện sắp xếp c&aacute;c phần tử với t&ecirc;n l&agrave; bubbleSort(), c&oacute; chứa một tham số đầu v&agrave;o l&agrave; một mảng tập hợp c&aacute;c phần tử cần sắp xếp. B&ecirc;n trong h&agrave;m, ch&uacute;ng ta sẽ sử dụng 2 v&ograve;ng lặp for, với v&ograve;ng lặp thứ 1 c&oacute; nhiệm vụ duyệt qua từng phần tử trong mảng v&agrave; v&ograve;ng lặp for thứ 2 c&oacute; nhiệm vụ thực hiện duyệt qua j phần tử. Một c&acirc;u lệnh điều kiện if được sử dụng để so s&aacute;nh giữa phần tử thứ j với phần tử j + 1, nếu phần tử thứ j lớn hơn phần tử thứ j + 1, thực hiện ho&aacute;n đổi 2 phần tử n&agrave;y cho nhau.
Như vậy, ch&uacute;ng ta đ&atilde; thực hiện xong thuật to&aacute;n sắp xếp nổi bọt bằng ng&ocirc;n ngữ lập tr&igrave;nh Python.

Admin

Xây dựng chương trình sử dụng thuật toán sắp xếp nổi bọt bằng Python

Cùng tác giả

Admin

Có liên quan