Programme C/C++ écrit à l'aide d'un algorithme de tri par fusion pour calculer le logarithme inverse dans un tableau ?

Le décompte d’inversion qui se produit lors du tri d’un tableau donné est appelé décompte d’inversion. Le problème inverse est un problème classique qui peut être résolu à l’aide de l’algorithme de tri par fusion. Dans ce problème v, nous compterons tous les éléments à sa gauche qui sont supérieurs à lui et ajouterons le nombre à la sortie. Cette logique est complétée dans la fonction de fusion du tri par fusion.

Pour mieux comprendre ce sujet, prenons un exemple. Considérons les deux sous-tableaux impliqués dans le processus de fusion -

Input: arr[] = { 1, 9, 6, 4, 5}
Output: Inversion count is 5

Explication

Nombre d'inversions d'un tableau

Donner n un tableau, trouver son inverse Nombre de tours. Si (i A[j]) alors la paire (i, j) est appelée l'inversion du tableau A. Nous devons compter toutes ces paires dans arr

Par exemple, il y a 5 inversions dans

tableau

(9,6), (9,4), (9,5), (6,4), (6 ,5)

1. Comparez les valeurs des éléments entre eux.

2. Si la valeur à l'index inférieur est plus élevée, incrémentez le compteur.

3. Affichez les résultats.

Exemple

#include <stdio.h>
int Merge(int arr[], int aux[], int low, int mid, int high) {
   int k = low, i = low, j = mid + 1;
   int inversionCount = 0;
   while (i <= mid && j <= high) {
      if (arr[i] <= arr[j]) {
         aux[k++] = arr[i++];
      } else {
         aux[k++] = arr[j++];
         inversionCount += (mid - i + 1); // NOTE
      }
   }
   while (i <= mid)
   aux[k++] = arr[i++];
   for (int i = low; i <= high; i++)
      arr[i] = aux[i];
   return inversionCount;
}
int MergeSort(int arr[], int aux[], int low, int high) {
   if (high == low) // if run size == 1
      return 0;
   int mid = (low + ((high - low) >> 1));
   int inversionCount = 0;
   inversionCount += MergeSort(arr, aux, low, mid);
   inversionCount += MergeSort(arr, aux, mid + 1, high);
   inversionCount += Merge(arr, aux, low, mid, high);
   return inversionCount;
}
int main() {
   int arr[] = { 1, 9, 6, 4, 5 };
   int N = 5;
   int aux[N];
   for (int i = 0; i < N; i++)
      aux[i] = arr[i];
   printf("Inversion count is %d", MergeSort(arr, aux, 0, N - 1));
   return 0;
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!