Сортировка слиянием на Python

Question

Решил я изучить алгоритмы и попробовал сделать сортировку слиянием. Руководился я видосиком где Тимофей Хирьянов объяснял.

n=0
#G=[int(input()) for m in range(n)]
G=[3,9,1,8,4,26,5,1,136]
def merge(A,B):
 i=0
 k=0
 j=0
 C=[0]*(len(A)+len(B))
 while i<len(A) and k<len(B):
    if A[i]<=B[k]:
     C[j]=A[i]
     i+=1
     j+=1
    else:
      C[j]=B[k]
      j=+1
      k+=1
 while i<len(A):
    C[j]=A[i]
    j=+1
    i+=1
 while k<len(B):
    C[j]=B[n]
    n=+1
    j+=1

def merge_sort(A):
    if len(A)<=1:
        return
    middle=len(A)//2
    L=[A[i] for i in range(0,middle)]
    R=[A[i] for i in range(middle,len(A))]
    merge_sort(L)
    merge_sort(R)
    C=merge(L,R)
    for i in G:
        A[i]=G[i]
        return A
merge_sort(G)

Вот ошибка Traceback (most recent call last): File "C:/Users/Daniil/PycharmProjects/program1/1.py", line 39, in merge_sort(G) File "C:/Users/Daniil/PycharmProjects/program1/1.py", line 33, in merge_sort merge_sort(L) File "C:/Users/Daniil/PycharmProjects/program1/1.py", line 33, in merge_sort merge_sort(L) File "C:/Users/Daniil/PycharmProjects/program1/1.py", line 37, in merge_sort A[i]=C[i] TypeError: 'NoneType' object is not subscriptable

Process finished with exit code 1

Answer 1

Если я правильно понял, в конце функции merge вам нужно вернуть значение, а вы ничего не возвращаете. Нужно сделать так:

def merge(A,B):
# ...
    return C

Если ничего не возвращать из функции merge, то после присваивания

C = merge(L,R)

у вас в переменной C будет None, на что у вас программа в итоге и ругается.

И ещё у вас, кажется, лишняя табуляция перед return A в функции merge_sort, и вообще там непонятно у вас, почему результат работы этой функции ничему в итоге не присваивается? И путаница между C и G тоже непонятна. В общем, "тут всю систему менять надо".

Answer 2

Если бы вы изучали не "видосик", а вдумчиво изучали теорию, то написали бы свой алгоритм примерно так:

G=[3,9,1,8,4,26,5,1,136]
def merge(A, B):
    Res = []
    i = 0
    j = 0
    while i < len(A) and j < len(B):
        if A[i] <= B[j]:
            Res.append(A[i]) 
            i += 1 
        else:
            Res.append(B[j]) 
            j += 1 
    Res += A[i:] + B[j:] 
    return Res
def merge_sort(A): 
    if len(A) <= 1: 
        return A 
    else:
        L = A[:len(A) // 2] 
        R = A[len(A) // 2:]
    return merge(merge_sort(L), merge_sort(R))
merge_sort(G)

Out[5]: [1, 1, 3, 4, 5, 8, 9, 26, 136]

БЛОГ НА HUSL

Сортировка слиянием на Python

Ответы (2 шт):