선택 및 삽입 정렬에서 비교 횟수를 계산하는 방법은 무엇입니까?

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 값을 얻을 수 있습니다. 그러나 올바르게 정렬 된 문자열 배열로 테스트 할 때 값이 0이됩니다. 올바른 경우 성능이 올바르지 않습니다. 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--; 
     } 
    } 
}