マージソートの逆数の数を計算する

Question

マージソートを実装しました。ソートも同様に元の配列のinversionsの数を計算したいと思います。

以下は、何らかの理由で逆転の回数を正しく計算できないという実装を試みたことです。

たとえば、mergeSort([4, 3, 2, 1])は、(6, [1, 2, 3, 4])を返す必要があります。

def mergeSort(alist): 
    count = 0 
    if len(alist)>1: 
     mid = len(alist)//2 
     lefthalf = alist[:mid] 
     righthalf = alist[mid:] 

     mergeSort(lefthalf) 
     mergeSort(righthalf) 

     i=0 
     j=0 
     k=0 

     while i < len(lefthalf) and j < len(righthalf): 
      if lefthalf[i] < righthalf[j]: 
       alist[k]=lefthalf[i] 
       i=i+1 
      else: 
       alist[k]=righthalf[j] 
       count +=len(lefthalf[i:]) 
       j=j+1  
      k=k+1 

     while i < len(lefthalf): 
      alist[k]=lefthalf[i] 
      i=i+1 
      k=k+1 

     while j < len(righthalf): 
      alist[k]=righthalf[j] 
      j=j+1 
      k=k+1 

    return count, alist 

Answer 1

。

def mergeSort(alist): 
    count = 0 
    leftcount = 0 
    rightcount = 0 
    blist = [] 
    if len(alist) > 1: 
     mid = len(alist) // 2 
     lefthalf = alist[:mid] 
     righthalf = alist[mid:] 
     leftcount, lefthalf = mergeSort(lefthalf) 
     rightcount, righthalf = mergeSort(righthalf) 

     i = 0 
     j = 0 

     while i < len(lefthalf) and j < len(righthalf): 
     if lefthalf[i] < righthalf[j]: 
      blist.append(lefthalf[i]) 
      i += 1 
     else: 
      blist.append(righthalf[j]) 
      j += 1 
      count += len(lefthalf[i:]) 

     while i < len(lefthalf): 
      blist.append(lefthalf[i]) 
      i += 1 

     while j < len(righthalf): 
      blist.append(righthalf[j]) 
      j += 1 
    else: 
     blist = alist[:] 

    return count + leftcount + rightcount, blist 

Answer 2

この関数は、（inversion、sortedlist）のタプルを返します。しかし、あなたの内部再帰呼び出しはこれを完全に無視しているので、トップレベルよりも下にあるすべての逆転は単純に捨てられ、カウントされません。あなたがクラスメートとこれを共有している場合

lc, lefthalf = mergeSort(alist[:mid]) 
    rc, righthalf = mergeSort(alist[mid:]) 
    count = count + lc + rc 

と、あなたはこれを使用することがあります。主な問題は、左右のソートの数を含めていなかった

def count_inversions(data): 
    count, result = mergeSort(data) 
    return count 

test_cases = [ 
    (3, [1,3,5,2,4,6]), 
    (590, [37, 7, 2, 14, 35, 47, 10, 24, 44, 17, 34, 11, 16, 48, 1, 39, 6, 33, 43, 26, 40, 4, 28, 5, 38, 41, 42, 12, 13, 21, 29, 18, 3, 19, 0, 32, 46, 27, 31, 25, 15, 36, 20, 8, 9, 49, 22, 23, 30, 45]), 
    (2372, [4, 80, 70, 23, 9, 60, 68, 27, 66, 78, 12, 40, 52, 53, 44, 8, 49, 28, 18, 46, 21, 39, 51, 7, 87, 99, 69, 62, 84, 6, 79, 67, 14, 98, 83, 0, 96, 5, 82, 10, 26, 48, 3, 2, 15, 92, 11, 55, 63, 97, 43, 45, 81, 42, 95, 20, 25, 74, 24, 72, 91, 35, 86, 19, 75, 58, 71, 47, 76, 59, 64, 93, 17, 50, 56, 94, 90, 89, 32, 37, 34, 65, 1, 73, 41, 36, 57, 77, 30, 22, 13, 29, 38, 16, 88, 61, 31, 85, 33, 54]), 
] 

def validate(): 
    for expected, data in test_cases: 
     answer = count_inversions(data) 
     if answer != expected: 
      print "FAILED VALIDATION -- actual:", answer, "expected:", expected, "data:", data 

validate()