Lỗi khi lập trình giải thuật mergesort bằng python

Duc_Vu2 · June 22, 2018, 11:19am

Mình đang viết chương trình cho thuật toán sắp xếp trộn bằng python bị lỗi “list index out of range”. Có ai biết chỉ giúp mình cách fix được ko ạ

def merge(arr, left, mid, right):
    i = left
    j = mid+1
    temp = []
    n = len(arr)
    while ((i<=mid) and (j<=right)):
        if (arr[i]<=arr[j]):
            temp.append(arr[i])
            i+=1
        else:
            temp.append(arr[j])
            j+=1
    if (i<=mid):
        temp.extend(arr[i:mid])
    if (j<=right):
        temp.extend(arr[j:right])
    for x in range(n):
        arr[x]=temp[x]

def mergesort(arr, left, right):
    if (left<right):
        mid = int((left+right)/2)
        mergesort(arr, left, mid)
        mergesort(arr, mid+1, right)
        merge(arr, left, mid, right)

arr = [9, 8, 10, 8, 11]
mergesort(arr, 0, len(arr)-1)
print(arr)

noname00 · June 22, 2018, 11:14am

Mình có chạy thử code của bạn thì temp = [8], n = 5. temp không có đủ n phần tử, do vậy khi truy cập vào temp[x] với x > 0 thì code văng lỗi.

Có một sự thật là khi bạn gán n = len(arr) thì n luôn cố định Với lại, thuật toán của bạn sai rồi.

Duc_Vu2 · June 22, 2018, 2:02pm

Mình nghĩ thuật toán đúng chứ bạn, python mình mới học, mình viết theo code của c++. Bạn nói rõ hơn được ko, list mình tưởng dùng append sẽ tự thêm phần tử bé hơn vào list temp trung gian

hungaya · June 22, 2018, 2:43pm

Mấy hôm nay siêng đột xuất, chạy tay cho bạn luôn nè

mergesort([9, 8, 10, 8, 11], 0, 4)

arr = [9, 8, 10, 8, 11]
if (0 < 4):
  2 = int((0 + 4)/2)
  mergesort(arr, 0, 2)
  mergesort(arr, 2 + 1, 4)
  merge(arr, 0, 2, 4)

mergesort(arr, 0, 2)

arr = [9, 8, 10, 8, 11]
if (0 < 2):
  1 = int((0 + 2)/2)
  mergesort(arr, 0, 1)
  mergesort(arr, 1 + 1, 2)
  merge(arr, 0, 1, 2)

mergesort(arr, 0, 1)

arr = [9, 8, 10, 8, 11]
if (0 < 1):
  0 = int((0 + 1)/2)
  mergesort(arr, 0, 0)
  mergesort(arr, 0 + 1, 1)
  merge(arr, 0, 1, 1)

mergesort(arr, 0, 0)

arr = [9, 8, 10, 8, 11]
if (0 < 0):
  pass

mergesort(arr, 0 + 1, 1)

arr = [9, 8, 10, 8, 11]
if (1 < 1):
  pass

merge(arr, 0, 1, 1)

i = 0
j = 1 + 1 = 2
temp = []
arr = [9, 8, 10, 8, 11]
n = len(arr) = 5

while 0 < 1 and 2 < 1:
  pass

if 0 < 1:
  temp.extend(arr[0:1])
  # temp = [9]

if 2 < 1:
  pass

for x in range(5):
  arr[x] = temp[x]

arr = [9, 8, 10, 8, 11]
temp = [9]

for x in range(5):
  arr[x] = temp[x]

arr = [9, 8, 10, 8, 11]
temp = [9]

arr[0] = temp[0]
arr[1] = temp[1] # list index out of range
arr[2] = temp[2] # list index out of range
arr[3] = temp[3] # list index out of range
arr[4] = temp[4] # list index out of range

Duc_Vu2 · June 22, 2018, 3:39pm

Cảm ơn bạn nhiều nhé, mình sửa được r, mình mới chuyển qua python nên chưa hiểu index của list lắm