Python : 내부 병합 정렬 구현 문제

Question

python3에서 내부 병합 정렬 알고리즘을 구현하고 있습니다. 코드는 입력 배열을 취하여 입력 배열의 길이가 둘 이상인 경우 해당 배열을 입력으로 분할하여 반복적으로 호출합니다. 그런 다음 두 개의 정렬 된 배열을 조인합니다. 여기에 코드의 코드를 테스트하는 경우 이제

def merge_sort(array): 

    """ 
    Input : list of values 
    Note : 
     It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. 
    Returns : sorted list of values 

    """ 

    def join_sorted_arrays(array1, array2): 

     """ 
     Input : 2 sorted arrays. 
     Returns : New sorted array 

     """ 

     new_array = [] # this array will contain values from both input arrays. 
     j = 0    # Index to keep track where we have reached in second array 
     n2 = len(array2) 

     for i, element in enumerate(array1): 
      # We will compare current element in array1 to current element in array2, if element in array2 is smaller, append it 
      # to new array and look at next element in array2. Keep doing this until either array2 is exhausted or an element of 
      # array2 greater than current element of array1 is found. 
      while j < n2 and element > array2[j]: 
       new_array.append(array2[j]) 
       j += 1 
      new_array.append(element) 
     # If there are any remaining values in array2, that are bigger than last element in array1, then append those to 
     # new array. 
     for i in range(j,n2): 
      new_array.append(array2[i]) 
     return new_array 

    n = len(array) 
    if n == 1: 
     return array 
    else: 
     # print('array1 = {0}, array2 = {1}'.format(array[:int(n/2)], array[int(n/2):])) 
     array[:int(n/2)] = merge_sort(array[:int(n/2)]) 
     array[int(n/2):] = merge_sort(array[int(n/2):]) 
     # print('array before joining : ',array) 
     array = join_sorted_arrays(array[:int(n/2)],array[int(n/2):]) 
     # print('array after joining : ',array) 
     return array 

이며,

a = [2,1,4,3,1,2,3,4,2,7,8,10,3,4] 
merge_sort(a) 
print(a) 
out : [1, 1, 2, 2, 3, 3, 4, 2, 3, 4, 4, 7, 8, 10] 

위의 함수에서 인쇄 제표의 주석을 경우, 당신은 단지 마지막 그 전에, A = 주어진 출력을 알 수 있습니다 join_sorted_arrays의 호출. 이 함수를 호출 한 후에 배열 'a'를 정렬해야합니다. 놀랍게도, 내가 다음과 같이한다면 출력은 정확합니다.

a = [2,1,4,3,1,2,3,4,2,7,8,10,3,4] 
a = merge_sort(a) 
print(a) 
out : [1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 7, 8, 10] 

왜 이런 일이 발생하는지 이해하려면 도움이 필요합니다. 초보자이므로 코딩 관행 등에 관한 다른 의견도 환영합니다.

Answer 1

당신은 당신이 더 이상 a의 값을 업데이트하지 않을

array = join_sorted_arrays(array[:int(n/2)],array[int(n/2):]) 

와 join_sorted_arrays()의 출력으로 array을 재 할당합니다.

당신이 인수 array로 a에서 통과가 array (일명 a)의 원래 값을 업데이트해야합니다 같은 기능에 array라는 이름의 모든 변수가 보일 이유, 그것은 이해할 본다. 대신 array = join_sorted_arrays(...)의 경우 변수에 merge_sort() 범위의 새 변수가 있습니다. 함수에서 array을 반환하면 새 값, 정렬 된 값 집합이 반환됩니다.

a에 대한 참조가 마지막 진술까지 수정되었으므로 print(a)과 merge_sort(a 이후로 달라 보입니다. 그러나 반환 된 값인 merge_sort()에서 마지막으로 정렬 된 출력 만 가져옵니다.

당신이 보면 그것은 명확 수 있습니다 :

b = merge_sort(a) 
print(a) # [1, 1, 2, 2, 3, 3, 4, 2, 3, 4, 4, 7, 8, 10] 
print(b) # [1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 7, 8, 10] 

참고 파이썬은 패스 참조에 의한 언어 아니라고, 그것은 실제로 무엇의 세부 조사해내는 것이 조금 이상한 일 수있다 처음에. 나는 항상 내가 돌아 왔을 때 그것이 어떻게 작동하는지 읽기 위해 돌아가고있다. 주제에 대한 많은 게시물이 있습니다.이 게시물은 귀하에게 유용 할 수 있습니다.
예 : this one 및 this one.