Сортировка слиянием в Python - RuntimeError: превышена максимальная глубина рекурсии

Question

Я работаю над сортировкой слиянием в Python.

Я проверил merge функцию. Массивы отлично сливаются.

Но в функции mergeSort появляется ошибка: ---

RuntimeError: превышена максимальная глубина рекурсии.

RuntimeError Traceback (самый последний вызов последний) в () 63 print (обр. [I]), 64 ---> 65 mergeSort (обр, 0, n-1) 66 отпечаток ("") 67 print ("Sorted Array is")

в mergeSort (arr, l, r) 53 м = л + (р-1) / 2 54 mergeSort (обр, л, м) ---> 55 mergeSort (обр, м + 1, г) 56 слияния (обр, л, м, р) 57

Что может быть возможной причиной этого?

def merge(arr,l,m,r):
    n1 = m-l+1
    n2 = r-m

    L = [0] * n1
    R = [0] * n2

    print("First List")
    for i in range(0,n1):
        L[i] = arr[i+l]
        print(L[i]), 


    print("")
    print("Second List")    
    for j in range(0,n2):
        R[j] = arr[j+m+1]
        print(R[j]),



    #Merging the temp arrays
    i = 0
    j = 0
    k = 0
    print("")
    print("Merged List ---------->")

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            print(arr[k]),
            i+=1
        else:
            arr[k] = R[j]
            print(arr[k]),
            j+=1
        k+=1

    while i<n1:
        arr[k] = L[i]
        i+=1
        k+=1

    while j<n2:
        arr[k] = R[j]
        print(arr[k])
        j+=1
        k+=1

def mergeSort(arr,l,r):
    if l<r:
        m = l+(r-1)/2
        mergeSort(arr,l,m)
        mergeSort(arr,m+1,r)
        merge(arr,l,m,r)


arr = [0,12,13,0,1,22]
n = len(arr)

mergeSort(arr,0,n-1)
print(" ")
print("Sorted Array is")
for i in range(0,n-1):
    print(arr[i])

Answer 1

Неверный способ вычисления m в mergeSort (вам нужно разделить пополам все выражение, а не только (r-1)). Измените его на:

m = (l+(r-1))/2

Поскольку вы вычисляли это неправильно, ваш метод вызывал сам себя рекурсивно снова и снова, пока максимальная глубина стека методов не была превышена и, таким образом, произошел сбой.

Answer 2

• Вы допустили основную ошибку. Python - это язык динамического типа
• Прежде чем перейти к тому, почему вы получили эту RecurssionError Run Time, вам нужно сделать одно изменение.
  Вместо m = l+(r-1)/2 напишите m = (l+r)/2
  Потому что когда вы вызывали mergeSort(arr,0,n-1) в то время, n-1 является последним значением индекса, и поэтому нет необходимости r-1 в m = l+(r-1)/2

Оператор деления по полу (//) VS Оператор нормального деления (/)

Теперь перейдем к главному: почему вы взяли, что RecurssionError вот ответ

• Когда вы делаете операцию, как

m = (l + r) / 2

Операция деления даст дробную часть, т.е. m будет рассматриваться как плавающая переменная
поэтому m никогда не будет 0 , это будет любое плавающее число, которое скажет что-то 0,123 или 2,122 или 1,0025

Поскольку с плавающей запятой, как m никогда не будет 0 , условие if if l<r: всегда будет истинным, и функция mergeSort () переходит в Бесконечный цикл и вот почему вы получили RunRime RecurssionERROR

Вы хотите m как целое число , а не с плавающей запятой , поэтому вместо m = (l + r ) / 2

Запись m = (l + r) // 2 оператор деления по полу (//) даст вам целочисленное значение, а ваш Функция mergeSort () не переходит в бесконечный цикл

Ваш код будет выполнен на этот раз без ошибок. Просто внесите одно изменение m = (l + r) // 2

НО НО НО ваша функция merge () не годится, она не дает отсортированный массив, данные теряются, а что-то еще печатается

Answer 3

Это потому, что когда вы вызываете функцию слияния, вы передаете l = 0 и r = длина списка. И независимо от того, каким будет ваш расчет, в любом случае вы будете меньше чем r.

 m = l+(r-1)/2