Ошибка получения индекса списка вне диапазона при использовании функции сортировки слиянием

Question

Я получаю List index out of range ошибку.Я также использовал GeeksforGeeks программу в качестве справочной информации, но все еще получил эту ошибку.Я не получаю ошибку, когда я запускаю это без использования его внутри Merge_Sort() функции.

def Merge(arr, p, q, r):
    n1 = q-p+1
    n2 = r-q
    L = [0]*n1
    M = [0]*n2

    for i in range(0, n1):
        L[i] = arr[p+i-1]
    for j in range(0, n2):
        M[j] = arr[q+j]
    i = 0
    j = 0
    for k in range(r-1):
        if L[i] <= M[j]:
            arr[k] = L[i]
            i = i+1
        else:
            arr[k] = M[j]
        j = j+1

def Merge_Sort(arr, p, r):
    if p < r:
        q = int((p+r)/2)
        Merge_Sort(arr, p, q)
        Merge_Sort(arr, q+1, r)
        Merge(arr, p, q, r)

ar = [5, 3, 6, 1, 2, 9, 7, 8]
n = len(ar)
Merge_Sort(ar, 1, n)
print(ar)

Error:
 line 14, in Merge
    if L[i]<=M[j]:

IndexError: list index out of range

Answer 1

Код неверен: есть некоторая путаница в значениях индекса и границах среза, а также в других ошибках:

• индексы массива начинаются с 0 в python, поэтому вы должны вызвать Merge_sort(ar, 0, n)

• длина среза n1 отключена на единицу, она должна быть n1 = q - p

• тест на рекурсию должен вычислять длину среза и повторяться только для срезов как минимум с 2 элементами.

• цикл слияния неверен: вы должны проверить, находятся ли i и j внутри срезов. Эффективный способ сделать это - заменить сравнение следующим тестом:

  if i < n1 and (j == n2 or L[i] <= M[j]):
  

• цикл слияния должен повторяться для k с p до r исключено, а не с 0 до r исключено

• код приращения для j выровнен неверно, необходимо сделать отступ еще на один шаг

Гораздо проще считать первый индекс включенным, а второй - исключенным. В сети слишком много учебников на разных языках, которые настаивают на других соглашениях, что неизменно вызывает замешательство у начинающих программистов.

Вот исправленная и упрощенная версия:

def Merge(arr, p, q, r):
    n1 = q - p
    n2 = r - q
    L = arr[p : q]
    M = arr[q : r]
    i = 0
    j = 0
    for k in range(p, r):
        if i < n1 and (j == n2 or L[i] <= M[j]):
            arr[k] = L[i]
            i = i + 1
        else:
            arr[k] = M[j]
            j = j + 1

def Merge_Sort(arr, p, r):
    if r - p >= 2:
        q = (p + r) // 2
        Merge_Sort(arr, p, q)
        Merge_Sort(arr, q, r)
        Merge(arr, p, q, r)

ar = [5, 3, 6, 1, 2, 9, 7, 8]
Merge_Sort(ar, 0, len(ar))
print(ar)

Обратите внимание, что вы можете еще больше упростить функцию MergeSort с помощью одного временного массива, если убедитесь, что левый срез всегда по крайней мере такой же, как правый срез:

def Merge(arr, p, q, r):
    tmp = arr[p : q]
    i = 0
    n = q - p
    while i < n:
        if q == r or tmp[i] <= arr[q]:
            arr[p] = tmp[i]
            i += 1
            p += 1
        else:
            arr[p] = arr[q]
            q += 1
            p += 1

def Merge_Sort(arr, p, r):
    if r - p >= 2:
        q = (p + r + 1) // 2
        Merge_Sort(arr, p, q)
        Merge_Sort(arr, q, r)
        Merge(arr, p, q, r)

ar = [5, 3, 6, 1, 2, 9, 7, 8]
Merge_Sort(ar, 0, len(ar))
print(ar)

Answer 2

Ваш код отличается от кода GeeksforGeeks. Я исправил функцию merge, чтобы соответствовать их. Вам нужно три петли:

1. Возьмите меньшие из первых элементов от L или M, пока либо L, либо M не станет пустым
2. Добавить элементы, оставшиеся в L (если есть)
3. Добавить элементы, оставшиеся в M (если есть)

Вам также нужна переменная, которая отслеживает текущий индекс в arr (k в данном случае).

Код GeeksforGeeks: https://www.geeksforgeeks.org/merge-sort/

Исправленный код Python:

def Merge(arr, p, q, r):
    n1 = q-p+1
    n2 = r-q
    L = [0]*n1
    M = [0]*n2

    for i in range(0,n1):
        L[i] = arr[p+i]
    for j in range(0, n2):
        M[j] = arr[q+1+j]
    i = 0
    j = 0
    # result index
    k = p

    # take smallest element until either L or M are empty
    while i < n1 and j < n2:
        if L[i]<=M[j]:
            arr[k] = L[i]
            i = i+1
        else:
            arr[k] = M[j]
            j = j+1
        k = k+1

    # write remaining elements from L
    while i < n1:
        arr[k] = L[i]
        i = i+1
        k = k+1

    # write remaining elements from M
    while j < n2:
        arr[k] = M[j]
        j = j+1
        k = k+1

def Merge_Sort(arr, p, r):
    if p < r:
        q = int((p+r)/2)
        Merge_Sort(arr, p, q)
        Merge_Sort(arr, q+1,r)
        Merge(arr, p, q, r)
ar = [5,3,6,1,2,9,7,8]
n = len(ar)
Merge_Sort(ar,0,n-1)
print(ar)

Если вы хотите использовать только один цикл, вы можете комбинировать все вышеперечисленное, как показано ниже (хотя это и снижает читабельность):

def Merge(arr, p, q, r):
    n1 = q-p+1
    n2 = r-q
    L = [0]*n1
    M = [0]*n2

    for i in range(0,n1):
        L[i] = arr[p+i]
    for j in range(0, n2):
        M[j] = arr[q+1+j]
    i = 0
    j = 0

    for k in range(n1+n2):
        if (i < n1 and j < n2 and L[i]<=M[j]) or j >= n2:
            arr[p+k] = L[i]
            i = i+1
        else:
            arr[p+k] = M[j]
            j = j+1

def Merge_Sort(arr, p ,r):
    if p < r:
        q = int((p+r)/2)
        Merge_Sort(arr, p, q)
        Merge_Sort(arr, q+1,r)
        Merge(arr, p, q, r)
ar = [5,3,6,1,2,9,7,8,]
n = len(ar)
Merge_Sort(ar,0,n-1)
print(ar)