マージソート用の比較カウンタをPythonで追加するには？

Question

私が使用しているコードは以下の通りです。

このコードに比較カウンターを追加したいが、私が今持っているものは、要素の数と同じ数を表示する。

def MergeSort(argShuffledList): 
    intNumOfComp = 0 
    if len(argShuffledList)>1: 
     intMidValue = len(argShuffledList)//2 
     listLeftHalf = argShuffledList[:intMidValue] 
     listRightHalf = argShuffledList[intMidValue:] 

     MergeSort(listLeftHalf) 
     MergeSort(listRightHalf) 

     i=0 
     j=0 
     k=0 
     while i < len(listLeftHalf) and j < len(listRightHalf): 
      if listLeftHalf[i] < listRightHalf[j]: 
       argShuffledList[k]=listLeftHalf[i] 
       i=i+1 
       intNumOfComp += 1 
      else: 
       argShuffledList[k]=listRightHalf[j] 
       j=j+1 
       intNumOfComp += 1 

      k=k+1 

     while i < len(listLeftHalf): 
      argShuffledList[k]=listLeftHalf[i] 
      i=i+1 
      k=k+1 
      intNumOfComp += 1 

     while j < len(listRightHalf): 
      argShuffledList[k]=listRightHalf[j] 
      j=j+1 
      k=k+1 
      intNumOfComp += 1 

    return argShuffledList, "Comparison Count: " + str(intNumOfComp) 

Answer 1

あなたは再帰を作って、そのため、あなたは左半分リストと右半分リストの比較を数えていません。改訂された正しいコードです。

def MergeSort(argShuffledList): 
    intNumOfComp = 0 

    if len(argShuffledList)>1: 
     intMidValue = len(argShuffledList)//2 
     listLeftHalf = argShuffledList[:intMidValue] 
     listRightHalf = argShuffledList[intMidValue:] 

     left_part = MergeSort(listLeftHalf) 
     right_part = MergeSort(listRightHalf) 

     intNumOfComp += left_part[1] + right_part[1] 

     i=0 
     j=0 
     k=0 
     while i < len(listLeftHalf) and j < len(listRightHalf): 
      intNumOfComp += 1 
      if listLeftHalf[i] < listRightHalf[j]: 
       argShuffledList[k]=listLeftHalf[i] 
       i =i+1 

      else: 
       argShuffledList[k]=listRightHalf[j] 
       j=j+1 

      k=k+1 

     while i < len(listLeftHalf): 
      argShuffledList[k]=listLeftHalf[i] 
      i=i+1 
      k=k+1 
      intNumOfComp += 1 

     while j < len(listRightHalf): 
      argShuffledList[k]=listRightHalf[j] 
      j=j+1 
      k=k+1 
      intNumOfComp += 1 

    return argShuffledList, intNumOfComp