MergeSortアルゴリズムを実行しましたが、スワップをカウントする方法がわかりません。
私のコードは：
def mergesortInv(list):
if len(list) < 2:
return list
else:
middle = len(list) // 2
left = mergesortInv(list[:middle]) #definim les dues meitats
right = mergesortInv(list[middle:])
swaps=???
return mergeInv(left, right,swaps)
def mergeInv(left, right,swaps):
if len(left) < 1:
return right
if len(right) < 1:
return left
if left[0] <= right[0]:
return [left[0]] + mergeInv(left[1:],right,swaps)
else:
return [right[0]] + mergeInv(left,right[1:],swaps)
このアルゴリズムの出力は、ソートされたリスト（アルゴリズムはこの部分で機能します）であり、スワップの数：mergesortInv(list) == ([1, 2, 3, 4, 5, 7, 8], 6)6はスワップの数です。
動作しているように見えるコードのわずかに変更されたバージョンを次に示します。
def mergesortInv(list, mergeInv):
if len(list) < 2:
return list, 0
else:
middle = len(list) // 2
left, lc = mergesortInv(list[:middle], mergeInv) #definim les dues meitats
right, rc = mergesortInv(list[middle:], mergeInv)
merge, mc = mergeInv(left, right)
return merge, lc + rc + mc
def mergeInvRec(left, right):
if len(left) < 1:
return right, 0
if len(right) < 1:
return left, 0
if left[0] <= right[0]:
res, cnt = mergeInvRec(left[1:], right)
return [left[0]] + res, cnt
else:
res, cnt = mergeInvRec(left, right[1:])
return [right[0]] + res, len(left) + cnt
def mergeInvFlat(left, right):
res, cnt = [], 0
il, ir = 0, 0
nl, nr = len(left), len(right)
while il < nl and ir < nr:
if left[il] <= right[ir]:
res.append(left[il])
il += 1
else:
res.append(right[ir])
ir += 1
cnt += nl - il
res.extend(left[il:])
res.extend(right[ir:])
return res, cnt
それは主に簿記の問題です。各ステップでのスワップの数を数え、それらを追加します。最後のブランチでは、rightバブルの最初の要素がすべての要素をはるかに超えleftているため、len(left)そこでスワップを集計します。
編集： @ PM2Ringが指摘しているように、の再帰mergeInvは少し無謀であり、適度なサイズのリストのPythonの最大再帰深度を超えます。非再帰バージョンを追加しました。main関数に2番目の引数として名前を渡すことにより、再帰バージョンと非再帰バージョンを切り替えることができます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加