Значение переменной неожиданно изменилось во время рекурсии (MERGE SORT)

Question

Учитывая входной массив:

[49, 86, 78]

Мой код должен возвращать:

[[49,1],[78,2],[86,1]]

То есть, он должен упорядочить массив в соответствии с первым номером в каждом подмассиве, второй один будет использоваться в качестве индекса для последующего использования. Я решил использовать сортировку слиянием для сортировки. Вот мой код (я знаю, что он уродлив, но, пожалуйста, запустите его один раз):

def merge_sort(array):
    print("array>>>", array)
    if len(array[:,0]) == 1:
        print('going back')
        return
    arrL = array[0:int(len(array)/2),:]
    arrR = array[int(len(array)/2):,:] 
    print('left>>', arrL, 'right>>', arrR)
    print("*****************")
    print('into left')
    merge_sort(arrL)
    print("*****************")
    print('into right')
    merge_sort(arrR)
    print("*****************")
    print('into MERGE')
    merge(array, arrL, arrR)
    print('going back')

def merge(A, arrL, arrR):
    print("array ", A, "left", arrL, "right", arrR)
    i = 0
    while len(arrL[:,0]) is not 0 and len(arrR[:,0]) is not 0:
        print('ARRAYLEFT>>', arrL, 'ARRAYRIGHT>', arrR)
        if arrR[0,0] < arrL[0,0]:
            print(arrR[0,0], 'is less than', arrL[0,0])
            A[i] = arrR[0]
            arrR = arrR[1:,:]
            print('A>>', A, 'arrR>>', arrR, 'ARRAYLEFT>>', arrL)
        else:
            print(arrL[0,0], 'is less than', arrR[0,0])
            A[i] = arrL[0]
            arrL = arrL[1:,:]
            print('A>>', A, 'arrL>>', arrL)
        i += 1

    print('ARRAYLEFT>>', arrL, 'ARRAYRIGHT>>', arrR)

    if len(arrL[:,0]) == 0 :
        print('left exhaused')
        print('A>>', A, 'arrR>>', arrR)
        A[i:,:] = arrR
        print('A>>', A, 'arrR>>', arrR)

    elif len(arrR[:,0]) == 0:
        print('right exhaused')
        print('A>>', A, 'arrL>>', arrL)
        A[i:,:] = arrL
        print('A>>', A, 'arrL>>', arrL)

    print('after merge', A)
    return 

---

import numpy as np
np.random.seed(1)
input_array = [np.random.choice(np.arange(100)) for _ in range(5)]
print(input_array)

выводит:

[37, 12, 72, 9, 75]

затем,

new_array = np.array(list( map(list, zip(input_array, [x for x in range(len(input_array)) ])) ))
print(new_array)

выводит:

array([[37,  0],
       [12,  1],
       [72,  2],
       [ 9,  3],
       [75,  4]])

и, наконец,

merge_sort(new_array)

дает следующее (я добавил только интересующую часть). Обратите внимание, как только мы go into MERGE меняем значение arrL на значение arrR, когда arrR становится [] помеченным в коде знаком <<<===:

array>>> [[37  0]
 [12  1]
 [72  2]
 [ 9  3]
 [75  4]]
left>> [[37  0]
 [12  1]] right>> [[72  2]
 [ 9  3]
 [75  4]]
*****************
into left
array>>> [[37  0]
 [12  1]]
left>> [[37  0]] right>> [[12  1]]
*****************
into left
array>>> [[37  0]]
going back
*****************
into right
array>>> [[12  1]]
going back
*****************
into MERGE
array  [[37  0]
 [12  1]] left [[37  0]] right [[12  1]]
ARRAYLEFT>> [[37  0]] ARRAYRIGHT>> [[12  1]]  <<<=== # arrL = [[37  0]]
12 is less than 37
A>> [[12  1]
 [12  1]] arrR>> [] ARRAYLEFT>> [[12  1]]
ARRAYLEFT>> [[12  1]] ARRAYRIGHT>> []       <<<=== # arrL = [[12  1]]
right exhaused
A>> [[12  1]
 [12  1]] arrL>> [[12  1]]
A>> [[12  1]
 [12  1]] arrL>> [[12  1]]
after merge [[12  1]
 [12  1]]
going back
*****************
## .... and so one....

Эта ошибка, кажется, возникает всякий раз, когда код идет into MERGE и arrR = [], поэтому после этого

print(new_array)

выводит:

array([[ 9,  3],
       [ 9,  3],
       [ 9,  3],
       [ 9,  3],
       [75,  4]])

, что является явно неправильным ответом. Пожалуйста, помогите мне понять, где я делаю ошибку ... Я смотрел на код и вывод в течение добрых 20 минут, но, похоже, не могу его найти. Любые предложения / критика будут высоко оценены.

Answer 1

Это довольно сложно понять, в основном из-за похожих печатных сообщений в разных местах. Кажется, проблема связана с тем, что A[0] и arrL - это одинаковые массивы. Это было бы не так для простых python списков, но numpy, похоже, выполняет какую-то оптимизацию для экономии памяти. Поэтому, когда вы изменяете A[i] = arrR[0], вы в основном назначаете arrL = arrR. Кроме того, реализация кажется довольно необычной для алгоритма сортировки слиянием. Вам не нужен ни NumPy, ни 2d массив, просто список чисел - это то, что вы хотите отсортировать. Если вы просто хотите отсортированный список, вы можете использовать встроенную реализацию sorted (array). Наконец, я бы любезно рекомендовал привыкнуть к отладчику (один в вашей IDE или PDB https://realpython.com/python-debugging-pdb/) вместо операторов print, это гораздо более эффективный способ понять, что делает код. Сначала это может быть сложно, но, поверьте мне, это окупится и поможет вам стать разработчиком. Оставайтесь в безопасности.

Answer 2

Добавление .copy () везде решало мою проблему.

def merge(A,arrL,arrR):
    i = 0
    while len(arrL[:,0]) is not 0 and len(arrR[:,0]) is not 0:
        if arrR[0,0] < arrL[0,0]:
            A[i] = arrR[0].copy()
            arrR = arrR[1:,:].copy()
        else:
            A[i] = arrL[0].copy()
            arrL = arrL[1:,:].copy()
        i+=1

    if len(arrL[:,0]) == 0 :
        A[i:,:] = arrR.copy()

    elif len(arrR[:,0]) == 0:
        A[i:,:] = arrL.copy()

    return 

def merge_sort(array):
    if len(array[:,0]) == 1:
        return
    arrL = array[0:int(len(array)/2),:].copy()
    arrR = array[int(len(array)/2):,:] .copy()
    merge_sort(arrL)
    merge_sort(arrR)
    merge(array,arrL,arrR)