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

Question

У меня возникли проблемы с подсчетом количества сравнений для mergesort в Java. Ниже мой код. Не уверен, помещаю ли я его в неправильное место и т. Д.

Любая помощь, безусловно, ценится, спасибо.

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

Если вы хотите посчитать количество сравнений, сделайте шаг сравнения, отредактируйте его методу и примените метод. Вы увеличиваете numComparisons в неположенном месте.

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

Используйте, что вместо вашей линии сравнения в верхней части merge.

Кроме того, напишите тесты JUnit, чтобы убедиться, что ваш вид работает. Наконец, вам нужно, чтобы все ваши методы были статичными?