<h2 style="text-align: justify;">1. C&aacute;ch thức hoạt động của thuật to&aacute;n QuickSort</h2>
<ul style="text-align: justify;">
<li>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>
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/7d2f8942-1c01-436e-aac3-ed9685ff2937" alt="thuat-toan-quicksort-1" />
<ul style="text-align: justify;">
<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>
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/c8db909c-61da-4f8d-a501-0aa0ce1f464b" alt="thuat-toan-quicksort-2" />
<ul style="text-align: justify;">
<li>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>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>Tiếp theo, phần tử Pivot được so s&aacute;nh với c&aacute;c phần tử kh&aacute;c. Nếu đi đế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>
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/b7bb6a80-4797-470e-a1d3-4a591a76b55e" alt="thuat-toan-quicksort-3" />
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/16153fe5-4edf-45db-af1c-4c3779eb107c" alt="thuat-toan-quicksort-4" />
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/73adc318-53fc-461e-aaa9-7ed044400a6a" alt="thuat-toan-quicksort-5" />
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/bb1dcbdf-b199-4e38-9f98-b4d1c46beb69" alt="thuat-toan-quicksort-6" />
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/1befc492-2c63-409d-a975-2d526f8c2b1f" alt="thuat-toan-quicksort-7" />
<ul style="text-align: justify;">
<li style="list-style-type: none;">
<ul>
<li>Qu&aacute; tr&igrave;nh tiếp tục cho đến khi đi đến đượ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>
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/aed56ebd-01bd-4794-a3e6-e1b2eaa2123a" alt="thuat-toan-quicksort-8" />
<ul style="text-align: justify;">
<li style="list-style-type: none;">
<ul>
<li>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>
<img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="../../../public_files/72e12b91-7112-4f56-a245-15baf8830f9e" alt="thuat-toan-quicksort-9" />
<ul style="text-align: justify;">
<li>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>Bước 5: L&uacute;c n&agrave;y, mảng đ&atilde; được sắp xếp theo thứ tự.</li>
</ul>
<h2 style="text-align: justify;"> 2. X&acirc;y dựng đoạn m&atilde; thực thi</h2>
Như vậy, ch&uacute;ng ta c&oacute; đoạn m&atilde; thực thi như sau:
<pre class="line-numbers language-python" tabindex="0"><code>def partition(array, low, high):
 #Chọn phần tử b&ecirc;n phải cuối c&ugrave;ng l&agrave;m phần tử pivot
 pivot = array[high]
 #Con trỏ cho phần tử lớn hơn
 i = low - 1
 #Duyệt qua tất cả c&aacute;c phần tử v&agrave; so s&aacute;nh với phần tử pivot
 for j in range(low, high):
 if array[j] &lt;= pivot:
 #Nếu phần tử nhỏ hơn pivot, thực hiện ho&aacute;n đổi với phần tử lớn hơn được trỏ bởi i
 i = i + 1
 #Ho&aacute;n đổi phần tử tại i với phần tử tại j
 (array[i], array[j]) = (array[j], array[i])
 #Ho&aacute;n đổi phần tử pivot với phần tử lớn hơn chỉ định bởi i
 (array[i + 1], array[high]) = (array[high], array[i + 1])
 #Trả về vị tr&iacute; m&agrave; ph&acirc;n v&ugrave;ng được thực hiện
 return i + 1

#H&agrave;m thực hiện sắp xếp quicksort
def quickSort(array, low, high):
 if low &lt; high:
 #T&igrave;m phần tử pivot sao phần tử nhỏ hơn pivot nằm b&ecirc;n tr&aacute;i v&agrave; lớn hơn nằm b&ecirc;n phải
 pi = partition(array, low, high)
 #Gọi đệ quy h&agrave;m với phần b&ecirc;n tr&aacute;i của pivot
 quickSort(array, low, pi - 1)
 #Gọi đệ quy h&agrave;m với phần b&ecirc;n phải của pivot
 quickSort(array, pi + 1, high)

data = [8, 7, 2, 1, 0, 9, 6]
print("Unsorted Array")
print(data)
size = len(data)
quickSort(data, 0, size - 1)
print('Sorted Array in Ascending Order:')
print(data)</code></pre>
Kết quả đầu ra:
<img style="width: 100%;" src="http://tek4vn.2soft.top/public_files/a-png-59" alt="a" />
Trong đoạn m&atilde; b&ecirc;n tr&ecirc;n, ch&uacute;ng ta thực hiện định nghĩa một h&agrave;m c&oacute; t&ecirc;n l&agrave; partition để thực hiện nhiệm vụ t&aacute;ch nhỏ mảng th&agrave;nh với 3 tham số đầu v&agrave;o. Tham số thứ 1 l&agrave; mảng cần sắp xếp, tham số thứ hai l&agrave; chỉ số đầu ti&ecirc;n của mảng v&agrave; tham số thứ 3 l&agrave; chỉ số cuối c&ugrave;ng của mảng.
B&ecirc;n trong h&agrave;m n&agrave;y, phần tử tại chỉ số cuối c&ugrave;ng của mảng sẽ được thiết lập l&agrave;m phần tử Pivot. Biến i đ&oacute;ng vai tr&ograve; l&agrave;m con trỏ cho phần tử lớn hơn.
Tiếp theo, ch&uacute;ng ta sẽ thực hiện duyệt qua từng phần tử trong mảng bằng c&aacute;ch sử dụng v&ograve;ng lặp for. B&ecirc;n trong v&ograve;ng lặp, nếu phần tử nhỏ hơn hoặc bằng phần tử Pivot, ch&uacute;ng ta sẽ thực hiện ho&aacute;n đổi n&oacute; với phần tử lớn hơn được trỏ bởi i. V&agrave; thực hiện ho&aacute;n đổi phần tử tại vị tr&iacute; thứ i với phần tử tại vị tr&iacute; thứ j.
Sau đu khi duyệt qua tất cả c&aacute;c phần tử, ch&uacute;ng ta thực hiện ho&aacute;n đổi phần tử Pivot với phần tử lớn hơn được trỏ bởi biến i v&agrave; trả về vị tr&iacute; nơi m&agrave; thao t&aacute;c t&aacute;ch mảng được thực hiện.
H&agrave;m thứ 2 được định nghĩa l&agrave; h&agrave;m quickSort c&oacute; nhiệm vụ thực hiện sắp xếp cho mảng. H&agrave;m n&agrave;y nhận v&agrave;o 3 tham số bao gồm tham số đầu ti&ecirc;n l&agrave; mảng cần sắp xếp, tham số thứ 2 l&agrave; chỉ số đầu ti&ecirc;n của mảng v&agrave; tham số cuối l&agrave; chỉ số cuối c&ugrave;ng trong mảng. B&ecirc;n trong h&agrave;m n&agrave;y, một c&acirc;u lệnh điều kiện if được sử dụng để so s&aacute;nh xem nếu chỉ số low &lt; high, ch&uacute;ng ta sẽ thực hiện t&igrave;m kiếm phần tử Pivot sao cho phần tử nhỏ hơn phần tử Pivot nằm ở b&ecirc;n tr&aacute;i v&agrave; phần tử lớn hơn phần tử Pivot nằm ở b&ecirc;n phải. Tiếp theo, ch&uacute;ng ta thực hiện gọi 2 h&agrave;m quickSort một c&aacute;ch đệ quy với tham số truyền v&agrave;o l&agrave; mảng, chỉ số đầu ti&ecirc;n của mảng v&agrave; vị tr&iacute; của phần tử Pivot trừ đi 1 đơn vị. Lời gọi đệ quy cho h&agrave;m quickSort thứ 2 bao gồm tham số đầu v&agrave;o l&agrave; mảng cần sắp xếp, chỉ số vị tr&iacute; của phần tử pi + 1 v&agrave; chỉ số cuối c&ugrave;ng của mảng.
Như vậy, ch&uacute;ng ta đ&atilde; x&acirc;y dựng xong chương tr&igrave;nh sắp xếp c&aacute;c phần tử trong mảng bằng phương ph&aacute;p QuickSort trong 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 Quicksort bằng Python

Cùng tác giả

Admin

Có liên quan