Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:
Đề bài – Cho một mảng, cần sắp xếp dùng Merge Sort bằng vòng lặp (iteration).
Đặt phần tử lớn nhất ở cuối. Lặp lại cho đến khi mảng sắp xếp xong.
Hãy quan sát giải pháp trong triển khai dưới đây:
Ví dụ
# cách lặp
def mergeSort(a):
current_size = 1
# duyệt mảng con
while current_size < len(a) - 1:
left = 0
# mảng con đang sắp xếp
while left < len(a) - 1:
mid = left + current_size - 1
right = min(2 * current_size + left - 1, len(a) - 1)
merge(a, left, mid, right)
left = left + current_size * 2
current_size = 2 * current_size
def merge(a, l, m, r):
n1 = m - l + 1
n2 = r - m
L = [0] * n1
R = [0] * n2
for i in range(0, n1):
L[i] = a[l + i]
for i in range(0, n2):
R[i] = a[m + i + 1]
i, j, k = 0, 0, l
while i < n1 and j < n2:
if L[i] > R[j]:
a[k] = R[j]
j += 1
else:
a[k] = L[i]
i += 1
k += 1
while i < n1:
a[k] = L[i]
i += 1
k += 1
while j < n2:
a[k] = R[j]
j += 1
k += 1
# Driver code
a = [2, 5, 3, 8, 6, 5, 4, 7]
mergeSort(a)
print("Mảng đã sắp xếp:")
for i in range(len(a)):
print(a[i], end=" ")
Kết quả
Mảng đã sắp xếp: 2 3 4 5 5 6 7 8
Kết luận
Trong bài này, chúng ta đã học cách làm chương trình Python Iterative Merge Sort.