Где ошибка в реализации алгоритма Merge-Sort?

Question

[Игнатов Степан]

Вот код алгоритма Merge-Sort:

from math import floor


def Merge(A, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    L = []
    R = []
    for i in range(n1):
        L.append(A[p + i])
    for j in range(n2):
        R.append(A[q + j + 1])
    L.append(100000000000000000000000000000000)
    R.append(100000000000000000000000000000000)
    i = 0
    j = 0
    for k in range(p, r + 1):
        if L[i] < R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
    return A


def Merge_Sort(A, p, r):
    if p < r:
        q = floor((p + 2) /2)
        Merge_Sort(A, p, q)
        Merge_Sort(A, q + 1, r)
        Merge(A, p, q, r)
    return A


A = [7, 6, 5, 4, 3, 2, 1, 0]
p = 0
r = 7
print(Merge_Sort(A, p, r))

Программа выдает:

Traceback (most recent call last):
  File "================", line 39, in <module>
    print(Merge_Sort(A, p, r))
  File "================", line 30, in Merge_Sort
    Merge_Sort(A, p, q)
  File "================", line 30, in Merge_Sort
    Merge_Sort(A, p, q)
  File "================", line 30, in Merge_Sort
    Merge_Sort(A, p, q)
  [Previous line repeated 994 more times]
  File "================", line 28, in Merge_Sort
    if p < r:
RecursionError: maximum recursion depth exceeded in comparison

Где ошибка? Брал алгоритм из хорошей книги

Answer 1

[Astrohas]

Питон, не одобряет рекурсию. Имеется ограничение на глубину. Дело в том что при каждом вызове функции рекурсивно, в памяти сохраняются объекты прежних вызовов, что может привести к переполнению стека (Stackoverflow)
Можно снять ограничение через sys.setrecursionlimit(n) где n нужное вам число.

Вот к примеру более адекватный пример mergesort-а:

def merge(left, right):
    if not left or not right:
        return left or right

    result = []
    i, j = 0, 0
    while (len(result) < len(left) + len(right)):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
        if i == len(left) or j == len(right):
            result.extend(left[i:] or right[j:])
            break
    return result


def mergesort(list):
    if len(list) < 2:
        return list

    middle = len(list) // 2
    left = mergesort(list[:middle])
    right = mergesort(list[middle:])

    return merge(left, right)


if __name__ == "__main__":
    print(mergesort([3, 4, 5, 1, 2, 8, 3, 7, 6]))

Comments

[Игнатов Степан]

Ну я снял ограничение ничего не изменилось

Answer 2

[Alex Setup]

from math import floor



def Merge(A, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    L = []
    R = []
    for i in range(n1):
        L.append(A[p + i])
    for j in range(n2):
        R.append(A[q + j + 1])
    L.append(100000000000000000000000000000000)
    R.append(100000000000000000000000000000000)
    i = 0
    j = 0
    for k in range(p, r + 1):
        if L[i] < R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
    return A


def Merge_Sort(A, p, r):
    if p < r:
        q = floor((p + r) /2)
        Merge_Sort(A, p, q)
        Merge_Sort(A, q+1 , r)
        Merge(A, p, q, r)
    return A



A = [7, 6, 5, 4, 3, 2, 1, 0]
p = 0
r = 7
print(Merge_Sort(A, p, r))

Answer 3

[Влад Григорьев]

Не знаю из какой хорошей книжки вы взяли алгоритм, но реализация у вас 100% не питоновская, и самое главное у вас всегда будет бесконечная рекурсия, так как вы вызываете функцию Merge_Sort(A, p, q), где у вас всегда p=0, а r=q=1, а условие выхода из рекурсии p

Comments

[Игнатов Степан]

И как это исправить?
Подскажите если Вам не тяжело

[Влад Григорьев]

посмотри тут там нормальное описние вроде как

[Игнатов Степан]

Влад Григорьев, Ну мне хотелось бы поправить данный вариант. Взят из книги Алгоритмы, Построение и Анализ (Кормен)

[Animkim]

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

[Влад Григорьев]

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