Блог

Главная - Вопросы по программированию - ошибка реализации сортировки слиянием python: превышена максимальная глубина рекурсии

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

#python #python-3.x #algorithm #sorting #mergesort

Вопрос:

Вот простой алгоритм сортировки слиянием, который я пытался реализовать на python. Я попытался сделать это без использования левых и правых параметров, которые можно найти в других местах, только с помощью срезов.

 from math import floor


def merge(A, B):
    """Mearges the two sorted lists A and B"""
    merged = []
    i, j = 0, 0
    while i < len(A) and j < len(B):
        if A[i] <= B[j]:
            merged.append(A[i])
            i  = 1
        else:
            merged.append(B[j])
            j  = 1
    
    if j == len(B):
        merged.extend(A[i:])
    elif i == len(A):
        merged.extend(B[j:])
    
    return merged

def merge_sort(A):
    if len(A) == 1:
        return A
    
    m = floor(len(A) / 2)
    half1 = A[0:m]    
    half2 = A[m:]
    A = merge_sort(half1)
    B = merge_sort(half2)
    R = merge(A, B)
    return R



def main():
    C = [6, 7, 2]
    print(merge_sort(C))
    exit()

if __name__ == "__main__":
    main()

И это прекрасно работало.
Но когда я попытался

 A = merge_sort(A[0:m])
B = merge_sort(A[m:])

вместо того, чтобы использовать переменные half1 и half2 merge_sort функции, я получил это:

 Traceback (most recent call last):
  File "/home/aayush/PyProgs/mrg_sort.py", line 44, in <module>
    main()
  File "/home/aayush/PyProgs/mrg_sort.py", line 40, in main
    print(merge_sort(C))
  File "/home/aayush/PyProgs/mrg_sort.py", line 32, in merge_sort
    B = merge_sort(A[m:])
  File "/home/aayush/PyProgs/mrg_sort.py", line 31, in merge_sort
    A = merge_sort(A[0:m])
  File "/home/aayush/PyProgs/mrg_sort.py", line 31, in merge_sort
    A = merge_sort(A[0:m])
  File "/home/aayush/PyProgs/mrg_sort.py", line 31, in merge_sort
    A = merge_sort(A[0:m])
  [Previous line repeated 993 more times]
  File "/home/aayush/PyProgs/mrg_sort.py", line 25, in merge_sort
    if len(A) == 1:
RecursionError: maximum recursion depth exceeded while calling a Python object

Пожалуйста, скажите мне, что я сделал не так.

Комментарии:

1. Я рекомендую: Начните отладку. Взгляните на параметры перед запуском программы и проверьте, содержат ли они то, что вы от них ожидаете.

2. Один незначительный момент: вам, вероятно, следует использовать if len(A) <= 1 . И: A = merge_sort(A[0:m]) изменяет A , поэтому B = merge_sort(A[m:]) использует измененное A , а не оригинальное.

3. Только что увидел это: в этом смысл ответа @sahasrara62.

Ответ №1:

вам просто нужно следить за именованием переменных, так как здесь A обновляется, и вы используете данные этого списка, а не исходные

 def merge_sort(A):
    if len(A) == 1:
        return A
    
    m = floor(len(A) / 2)
    c = merge_sort(A[0:m])
    B = merge_sort(A[m:])
    R = merge(c, B)
    return R

Ответ №2:

Вы пробовали работать с меньшими данными ?

Попробуй :

импорт sys sys.setrecursionlimit(10000)

Затем повторите попытку, если алгоритм не завершен, у вас бесконечный цикл

Метки: