Nombre de comparaisons pour MergeSort Java

Question

J'ai du mal à compter le nombre de comparaisons pour mergesort en Java. Voici mon code. Je ne sais pas si je le place au mauvais endroit, etc.

Toute aide est certainement appréciée, merci.

private static int merge(int[] intArray, int first, int n1, int n2) { 
    int numComparisons = 0; 
     int[] temp = new int[n1+n2]; 
     int copied = 0, copied1 = 0, copied2 = 0; 
     while((copied1 < n1) && (copied2 < n2)){ 
      if (intArray[first + copied1] < intArray[first + n1 + copied2]) { 
       temp[copied++] = intArray[first + copied1++]; 
      } 
      else { 
       temp[copied++] = intArray[first + n1 + copied2++]; 
      } 

     } 

     while(copied1 < n1)  { 
      temp[copied++] = intArray[first + copied1++]; 
     } 
     while(copied2 < n2)  { 
      temp[copied++] = intArray[first + n1 +copied2++]; 
     } 


     for(int i = 0; i < n1+n2; i++) { 
      numComparisons++; 
      intArray[first + i] = temp[i]; 
     } 

     return numComparisons; 
    } 


    public static int mergeSortComparisons(int[] intArray, int first, int last){ 
     int n1, n2; 
     if (last > 1){ 

      n1 = last/2; 
      n2 = last - n1; 

      mergeSortComparisons(intArray, first, n1); 
      mergeSortComparisons(intArray, first + n1, n2); 

      merge(intArray, first, n1, n2); 
     } 

     return first; 
    } 

Answer 1

Si vous voulez compter le nombre de comparaisons, passer à l'étape de comparaison, refactoriser à une méthode, et l'instrument de la méthode. Vous incrémentez numComparisons au mauvais endroit.

private static boolean lessThan(int[] ia, int leftIndex, int rightIndex) { 
    numComparisons++; 
    return ia[leftIndex] < ia[rightIndex]; 
} 

Utilisez qu'au lieu de votre ligne de comparaison près du sommet de merge. Également, écrivez des tests JUnit pour vous assurer que votre tri fonctionne. Enfin, avez-vous besoin que toutes vos méthodes soient statiques?