В чем проблема с этим алгоритмом сортировки слиянием? - PullRequest
Новая
       3

В чем проблема с этим алгоритмом сортировки слиянием?

0 голосов
/ 08 июня 2019

Я пытаюсь реализовать код Python для алгоритма сортировки слиянием, используя рекурсивные функции в Python.Но код работает не так, как ожидалось.Значение q в коде не уменьшается, как ожидается, оно застревает на 1-ом значении, и функция падает в бесконечную рекурсивную функцию. 

def merge(A,p,q,r):
    """ This function merges 2 sorted subarrays A[p .. q] and A[q+1 .. r] into a single sorted array A[p .. r]"""
    A1 = A[p:q]
    A2 = A[q:r]
    A1 = A1 + [max(A)+1]
    A2 = A2 + [max(A)+1]
    #print(A1,A2)
    i, j = 0,0
    for k in range(p,r):
        if(A1[i]<=A2[j]):
            A[k] = A1[i]
            i+=1
        else:
            A[k] = A2[j]
            j+=1
        #print(i,j,k)
        #print(A)
    return A

def mrgSort(A,p,r):
    r=len(A)
    if(p<(r-1)):
        q = (p+r)//2
        print(q)
        A1 = mrgSort(A,p,q)
        #print(A)
        A2 = mrgSort(A,q,r)
        #print(A)
        A = [A1,A2]
        merge(A,p,q,r)
        #print(A)  
    return A


print(mrgSort([0,3,2,-1,9,5,6,2,1],0,9))
#print(merge([0,3,5,10,-1,1,5,7,9],0,4,9))

1 Ответ

0 голосов
/ 08 июня 2019 
def merge(A,p,q,r):
    """ This function merges 2 sorted subarrays A[p .. q] and A[q+1 .. r] into a single sorted array A[p .. r]"""
    A1 = A[p:q]
    A2 = A[    q:r]

    A1 = A1 + [(max(A)+1)]
    A2 = A2 + [(max(A)+1)]
    i, j = 0,0
    for k in range(p,r):
         if A1[i]<=A2[j]:
            A[k] = A1[i]
            i+=1
        else:
            A[k] = A2[j]
            j+=1
return A

def mrgSort(A,p,r):
    if(p<(r-1)):
        q = (p+r)//2
        A = mrgSort(A,p,q)
        A = mrgSort(A,q,r)
        A = merge(A,p,q,r)
    return A

Некоторые ошибки, которые вы делаете:

  • Выполнение r=len(A) сбрасывает вашу переменную r каждый раз.

  • A = [A1, A2] дает вам список списков.Если вы хотите объединить списки, выполните: A = A1 + A2

  • Использование конкатенации A1 en A2 было неверным, если вы посмотрите на способ реализации алгоритма.

...