сортировка слиянием в python IndexError

Question

В моей реализации сортировки слиянием с использованием python во время выполнения произошла ошибка:

IndexError: list assignment index out of range

Вот код:

#merge
def merge(array, low, mid, high):
   n1 = mid - low + 1
   n2 = high - mid
   ll = [] * n1
   rr = [] * n2
   for i in range(n1):
      ll[i] = array[low + i]
   for j in range(n2):
      rr[j] = array[mid + 1 + j]

   (i, j) = (0, 0)
   k = low

   while i < n1 and j < n2:
      if ll[i] <= rr[j]:
         array[k] = ll[i]
         i = i + 1
      else:
         array[k] = rr[j]
         j = j + 1
   k = k + 1
   #for remaining members of the lists
   while i < n1:
      array[k] = ll[i]
      i = i + 1
      k = k + 1                

   while i < n2:
      array[k] = rr[j]
      j = j + 1
      k = k + 1  

метод сортировки слиянием

def mergesort(array, low, high):
   if low < high:
      mid = low + (high - low) // 2

      #recurrence
      mergesort(array, low, mid)
      mergesort(array, mid + 1, high)
      merge(array, low, mid, high)

драйвер

array = [ 74, 32, 89, 55, 21, 64 ]
mergesort(array, 0, len(array))    

во время выполнения кода появляется сообщение об ошибке IndexError: list assignment index out of range

Answer 1

Вы передаете длину массива в качестве второго аргумента merge, но функция merge, похоже, ожидает, что индекс последнего элемента в диапазоне будет отсортирован.

Этот API-интерфейс classi c, но он плохо выбран, поскольку вы не можете указать пустой диапазон, и он менее регулярный, требующий некоторых дополнительных настроек (+ 1 и - 1 для размеров подмассива и c.). Вы должны изменить код так, чтобы high был индексом первого элемента после диапазона, который нужно отсортировать.

В функции merge есть другие проблемы:

• неверны вычисления для размеров подмассива
• Вы увеличиваете k за пределы while l oop: k = k + 1 следует увеличивать на уровне глубже.
• последний l oop должен использовать j вместо i в качестве индекса.
• эта реализация использует рекурсию , а не рекурсию

Вот модифицированная версия:

def merge(array, low, mid, high):
   n1 = mid - low
   n2 = high - mid
   ll = [] * n1
   rr = [] * n2
   for i in range(n1):
      ll[i] = array[low + i]
   for j in range(n2):
      rr[j] = array[mid + j]

   i = 0
   j = 0
   k = low

   while i < n1 and j < n2:
      if ll[i] <= rr[j]:
         array[k] = ll[i]
         i = i + 1
      else:
         array[k] = rr[j]
         j = j + 1
      k = k + 1

   #copy the remaining members of the lists
   while i < n1:
      array[k] = ll[i]
      i = i + 1
      k = k + 1                

   while j < n2:
      array[k] = rr[j]
      j = j + 1
      k = k + 1  

def mergesort(array, low, high):
   if high - low > 1:
      mid = low + (high - low) // 2

      #recursion
      mergesort(array, low, mid)
      mergesort(array, mid, high)
      merge(array, low, mid, high)

Answer 2

В вашем коде есть некоторые ошибки, исправленная версия выглядит так (фиксированные строки комментируются):

слияние

def merge(array, low, mid, high):
    n1 = mid - low + 1
    n2 = high - mid
    ll = [0] * n1  # here
    rr = [0] * n2  # here

    for i in range(n1):
        ll[i] = array[low + i]
    for j in range(n2):
        rr[j] = array[mid + 1 + j]

    i, j = 0, 0
    k = low

    while i < n1 and j < n2 :
        if ll[i] <= rr[j]:
           array[k] = ll[i]
           i += 1
        else:
           array[k] = rr[j]
           j += 1
        k += 1
    while i < n1:
       array[k] = ll[i]
       i += 1
       k += 1

    while j < n2:  # here
      array[k] = rr[j]
      j += 1
      k += 1  

mergesort

def mergesort(array, low, high):
   if low < high:
        mid = (low + (high - 1)) // 2  # here

        mergesort(array, low, mid)
        mergesort(array, mid + 1, high)
        merge(array, low, mid, high)

и последний вызов функции:

array = [74 , 32 , 89 , 55 , 21 , 64]
mergesort(array , 0 , len(array) - 1)  # here