Bắt đầu ngayBắt đầu miễn phí

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

Xem khóa học

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)
Chỉnh sửa và Chạy Mã