Sửa lỗi trong thuật toán merge sort
Bạn được cung cấp một chương trình sắp xếp danh sách số bằng thuật toán merge sort. Khi kiểm thử hàm merge_sort(), bạn nhận ra mã chưa đúng. Bạn có thể sửa thuật toán để nó hoạt động chính xác không?
Bài tập này là một phần của khóa học
Cấu trúc dữ liệu và Thuật toán với Python
Hướng dẫn bài tập
- Sửa lỗi khi gán nửa bên trái.
- Sửa lỗi khi gán nửa bên phải.
- Sửa lỗi khi cập nhật con trỏ cho nửa bên trái.
- Sửa lỗi khi cập nhật con trỏ cho nửa bên phải.
Bài tập tương tác thực hành trực tiếp
Hãy thử làm bài tập này bằng cách hoàn thành đoạn mã mẫu này.
def merge_sort(my_list):
if len(my_list) > 1:
mid = len(my_list)//2
left_half = my_list[:mid]
right_half = my_list[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
# Correct mistake when assigning left half
my_list[k] = right_half[i]
i += 1
else:
# Correct mistake when assigning right half
my_list[k] = left_half[j]
j += 1
k += 1
while i < len(left_half):
my_list[k] = left_half[i]
# Correct mistake when updating pointer for left half
j += 1
k += 1
while j < len(right_half):
my_list[k] = right_half[j]
# Correct mistake when updating pointer for right half
i += 1
k += 1
my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)