Merge_Sortアルゴリズムのカウント作業

Question

すべて、アレイのソート方法をマージソートアルゴリズムを使用してカウントしたいと思います。 Merge Sortを使用して配列を配置することはできますが、処理中に必要な反転の数を数え続けるのは難しいです。

たとえば、[9,4,8​​,3]を入力すると、出力[3,4,8,9]と4つの反転が得られます。逆の定義は次のとおりである。もしBの中のb、Cのc、そしてb> cならば反転が必要である（B、Cの順番）。まず、1つの反転を個別に示す2つの部分（[4,9]、1）と（[3,8]、1）を取得します。そして、再びマージすると、4つのうち3つを選択し、9の代わりに8を選びます。

私の主な質問はアルゴリズムそのものに関係しないかもしれません。私の変数の1つを関数の関数ループ内に進化させる方法についてです。 （Merge_Sort関数内でMerge_Sort関数を使用しています）

def Merge_Sort(a): 
    n = len(a) 
    if n==1: 
     if not 'total_rev' in vars():    
      total_rev = 0 
     else: 
      total_rev += rev_ind 
    return a , total_rev 
    else: 
     m = math.floor(n/2) 
     b , rev_ind_b = Merge_Sort(a[:m]) 
     if not 'total_rev' in vars(): 
      total_rev = 0 
     else: 
      total_rev += rev_ind_b 
     c , rev_ind_c = Merge_Sort(a[m:]) 
     if not 'total_rev' in vars(): 
      total_rev = 0 
     else: 
      total_rev += rev_ind_c  
     a_sort , rev_ind = Merge(b,c) 
     if not 'total_rev' in vars(): 
      total_rev = 0 
      total_rev += rev_ind 
     else : 
      total_rev += rev_ind 
     return a_sort , total_rev 

def Merge(b,c): 
    p = len(b) 
    q = len(c) 
    d = [] 
    reverse_ind = 0 
    while len(b)!=0 or len(c)!=0 : 
     if (len(b)*len(c) != 0) : 
      b0 = b[0] 
      c0 = c[0] 
      if b0 <= c0 : 
       d.append(b0) 
       b.remove(b[0]) 
      else : 
       reverse_ind += 1 
       d.append(c0) 
       c.remove(c[0]) 
     else : 
      d.extend(b) 
      b=[] 
      d.extend(c) 
      c=[] 
    return d,reverse_ind 

マージ機能はうまくいきます。唯一の質問は、私が望むように変数total_invを更新することができないということです。私は定義されていないときはいつでも "total_inv"を定義しようとします。私のコードが乱雑になったので、それが良い方法であるかどうかは分かりません。私もグローバル変数を使用しようとするが、うまく動作しない。ありがとうございました！

Answer 1

それはより簡単である：

• 最深再帰レベル（n==1）にだけスワップの数は0を返す場合。論理はリストのスワップ数をその再帰レベルでで返す必要があります。大きなリストが何であるかは考慮されていません。だからn==1あなたのリストには明らかにスワップする必要のない1つの値があります。
• 他の場合は、再帰呼び出しから取得したカウントを加算します。そうすることで、再帰ツリーをバブリングするときにそれらが増加します。ここで

Merge_Sortのための適応コードされています

def Merge_Sort(a): 
    n = len(a) 
    if n==1: 
     return a, 0 # at deepest recursion always return 0 for the number of swaps 
    else: 
     m = n//2 # use integer division; you don't need `math.floor` 
     b , rev_ind_b = Merge_Sort(a[:m]) 
     c , rev_ind_c = Merge_Sort(a[m:]) 
     a_sort , rev_ind = Merge(b,c) 
     return a_sort , rev_ind_b + rev_ind_c + rev_ind # add the numbers