Подсчет количества инверсий в сортировке слияния

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

Ваша функция возвращает кортеж (инверсия, отсортированный список). Однако ваши внутренние рекурсивные вызовы полностью игнорируют это, поэтому любые инверсии, которые вы считаете ниже верхнего уровня, просто отбрасываются и не учитываются.

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()