Как подсчитать сравнения в сортировке и сортировке?

Question

Я пишу 2 разных вида, один выбор другой вставка. Ниже приведен мой метод сортировки вставки

public static void iSort(String[] array) 
{ 
    int i, j, k; 
    String temp; 
    for(i = 1; i<array.length; i++) 
    { 
    k=i; 
    for(j = k-1; j>=0 && array[j].compareTo(array[k])>0; j--) 
    { 
    ccounter++; 
    temp = array[j]; 
    array[j] = array[k]; 
    array[k] = temp; 
    k--; 
    } 
    } 
} 

где ccounter - это статическая переменная класса. Когда я тестирую это, используя массив строк из 1000 элементов, я получаю значение 239507. Однако, когда я тестирую с правильно упорядоченным массивом строк, я получаю нулевое значение, которое, как я знаю, неверно, так как наилучшая производительность n сравнений для n условий. Интересно, неправильно ли написан мой метод или если счетчик помещен неправильно

Answer 1

Проблема в том, что если вы выйдете из цикла, потому что compareTo() вернул false, вы не считаете это окончательное сравнение.

Если бы я писал это, я бы обернул код сравнения в функцию, которая вызывала бы compareTo() и увеличивала счетчик. Затем я использовал бы эту функцию обертки, чтобы выполнить все сравнения. Таким образом, нет никаких ошибок в расчете.

Answer 2

приращение счетчика для каждого выполнения внутреннего цикла и сделать сравнение после того, как приращение счетчика

public static void iSort(String[] array) 
{ 
    int i, j, k,ccounter=0; 
    String temp; 
    for(i = 1; i<array.length; i++) 
    { 
     k=i; 
     for(j = k-1; j>=0; j--) 
     { 
       ccounter++; //increment counter for every execution of inner loop 
       //better to do integer comparison than string comparison 
       if(Integer.parseInt(array[j]) <= Integer.parseInt(array[k])) 
       { 
        break; 
       } 
       temp = array[j]; 
       array[j] = array[k]; 
       array[k] = temp; 
       k--; 
     } 
    } 
}