マージソートアルゴリズムを使用して、配列がどれだけ近くにソートされているかを数えたいと思います。マージソートを使用して配列を配置することはできますが、プロセス中に必要な反転の数を数え続けるのに問題があります。
たとえば、入力[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）を取得します。次に、それらが再びマージされると、さらに2つの反転があります。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」が定義されていないときはいつでも定義しようとしています。それが私のコードを乱雑にしたので、それが良い方法であるかどうかはわかりません。私もグローバル変数を使おうとしていますが、うまくいきません。ありがとうございました！
それよりも簡単です：
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
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加