mergesort의 inversions 카운팅

Question

제대로 작동하는 mergesort 함수를 구현했습니다. 그러나 정렬되기 전에 원래 배열의 역전 수를 계산하기가 어렵습니다. i < j but a[i] > a[j] 예는 a = [5,2,1] 3 역전 갖는 경우

반전이 쌍 : 위의 예에서는 n은 반전의 횟수로 (15)를 반환한다 (5,2),(5,1),(2,1)

def mergeSort(a): 

    mid = len(a)//2 

    if len(a) < 2: 
     return 

    l = a[:mid] 
    r = a[mid:] 
    mergeSort(l) 
    mergeSort(r) 

    return merge(l,r,a) 

def merge(l,r,a): 
    i = 0 
    j = 0 
    k = 0 

    inv = 0 

    while(i < len(l) and j < len(r)): 
     if(l[i] < r[j]): 
      a[k] = l[i] 
      i = i + 1 
     else: 
      a[k] = r[j] 
      inv = inv + 1 
      j = j + 1 
     k = k + 1 

    while i < len(l): 
     a[k] = l[i] 
     i = i + 1 
     k = k + 1 
    while j < len(r): 
     a[k] = r[j] 
     j = j + 1 
     k = k + 1 
     inv = inv + 1 
    return [a,inv] 

a = [6,5,4,3,2,1] 
print(mergeSort(a)) 

을 (N-1)/2의 수이다 내림차순 정렬을위한 역변환.

누군가가 그것을 계산하는 방법을 설명 할 수 있습니까?

Answer 1

L[i] > R[j]은 단일 반전이지만 배열이 정렬되어 있으므로 의 경우 L[k] > R[j]이면 L[k] > R[j] for all i <= k < |L|을 의미합니다. 따라서 배열의 길이를 i에서 뺄셈하면 총 역전 횟수를 얻을 수 있습니다.