Python：インプレースマージソート実装の問題

Question

私はインプレースマージソートアルゴリズムをpython3で実装しています。コードは入力配列をとり、入力配列の長さが複数の場合は、それを自己再帰的に（分割配列を入力として）呼び出します。その後、2つのソートされた配列を結合します。ここでは、コードのコードがテストされている場合今

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] 

あなたは上記の関数ではprint文のコメントを解除した場合、あなただけの最後のその前に、=与えられた出力を、気づくでしょう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] 

なぜこれが起こっているのか理解するためには、何か助けが必要です。 私は初心者ですので、コーディングの実践などについての他のコメントも歓迎します。あなたはもうaの値を更新していない

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

でjoin_sorted_arrays()の出力としてarrayを再割り当て

Answer 1

。

あなたは引数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] 

注Pythonは参照渡しの言語ではないということ、そしてそれが実際に何であるかの詳細が出てズースには少し奇妙なことができます最初は。私はいつも、私がうまく立ち上がったときの仕組みを読むために戻っています。トピックには多くのSOの投稿がありますが、ここではあなたの役に立つかもしれません。
たとえば、this oneおよびthis one。