Comptage du nombre d'inversions dans un tableau donné

Question

J'ai essayé de résoudre ce problème en utilisant le tri par fusion, mais il y a un problème avec ma solution. J'ai vérifié le nombre d'inversions en fusionnant le tableau. Quelqu'un peut-il m'aider à trouver le problème?

void merge(int arr[], int l, int m, int r) 
{ 
    int n1=m-l+1; 
    int n2=r-m; 
    int left[(n1+1)]; 
    int right[(n2+1)]; 
    for(int i=0;i<n1;i++){ 
     left[i]=arr[l+i]; 
    } 
    for(int j=0;j<n2;j++){ 
     right[j]=arr[m+j+1]; 
    } 
    left[n1]=INT_MAX; 
    right[n2]=INT_MAX; 
    int i=0, j=0; 
    //int inv=0; 
    for(int k=l;k<=r;k++){ 
     if(left[i]<=right[j]){ 
      arr[k]=left[i]; 
      i++; 
     } 
     else{ 
      arr[k]=right[j]; 
      j++; 
      inv+=(m-i); 
     } 
    } 
    //return inv; 
} 

void mergeSort(int arr[], int l, int r) { 
    int inv=0; 
    if (l < r) { 
     int m = l+(r-l)/2; 
     mergeSort(arr, l, m); 
     mergeSort(arr, m+1, r); 
     merge(arr, l, m, r); 
    } 
    // return inv; 
} 

Answer 1

Vous faites tout correctement, sauf que vous devez ajouter n1 - i-inv instad de m - i.

Le raisonnement sous-jacent est le suivant. Quand vous prenez un nombre de la partie "droite", il est plus bas que n'importe quel nombre de la partie "gauche" qui n'a pas encore été prise, et ainsi de telles paires forment des inversions. Le nombre d'éléments non pris de la partie "gauche" est n1 - 1 [dernier numéro du tableau actuel. INT_MAX est stocké à l'index n1] - i [article non mis à jour] + 1 [parce que les index sont inclus], ce qui simplifie à n1 - i.

S'il vous plaît noter également que le nombre d'inversions peut être aussi élevé que O(n^2), où n est la taille du tableau, donc vous pouvez stocker le nombre d'inversions dans une variable long long.

La version finale du code:

int merge(int arr[], int l, int m, int r) 
{ 
    int n1=m-l+1; 
    int n2=r-m; 
    int left[(n1+1)]; 
    int right[(n2+1)]; 
    for(int i=0;i<n1;i++){ 
     left[i]=arr[l+i]; 
    } 
    for(int j=0;j<n2;j++){ 
     right[j]=arr[m+j+1]; 
    } 
    left[n1]=INT_MAX; 
    right[n2]=INT_MAX; 
    int i=0, j=0; 
    int inv=0; 
    for(int k=l;k<=r;k++){ 
     if(left[i]<=right[j]){ 
      arr[k]=left[i]; 
      i++; 
     } 
     else{ 
      arr[k]=right[j]; 
      j++; 
      inv += n1 - i; 
     } 
    } 
    return inv; 
} 

int mergeSort(int arr[], int l, int r) { 
    int inv=0; 
    if (l < r) { 
     int m = l+(r-l)/2; 
     inv += mergeSort(arr, l, m); 
     inv += mergeSort(arr, m+1, r); 
     inv += merge(arr, l, m, r); 
    } 
    return inv; 
}